论文标题
分析完全等效关系的学位光谱
Degree spectra of analytic complete equivalence relations
论文作者
论文摘要
我们研究了可降低鲍尔尔（Borel）降低性图的双重性能和基本双重性关系，并研究了该关系所实现的度光谱。我们首先从图表上的嵌入性降低到图形上的基本嵌入性。结果，我们获得了图上的基本双重性能是一个分析性完全对等关系。然后，我们研究了此还原的算法特性，以表明图形的每个双重性频谱都是图形的基本双重符合性谱的跳跃频谱。
We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by this relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a analytic complete equivalence relation. We then investigate the algorithmic properties of this reduction to show that every bi-embeddability spectrum of a graph is the jump spectrum of an elementary bi-embeddability spectrum of a graph.
