The Ramsey theory of the universal homogeneous triangle-free graph
The Ramsey theory of the universal homogeneous triangle-free graph
复制标题
DOI：
10.1142/s0219061320500129
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Natasha Dobrinen
中科院分区：
文献类型：
--
作者：
Natasha Dobrinen
通用齐次无三角形图，由 Henson 构建[可数齐次图族，Pacific J. Math. 38(1) (1971) 69–83] 并表示为[公式：参见文本]，是 Rado 图的无三角形类似物。虽然 Rado 图的 Ramsey 理论已经完全建立，但从 Erdős–Hajnal–Posá [在无限和有限集中图到彩色图的强嵌入]开始。卷[公式：见正文]，编辑。 A. Hajnal、R. Rado 和 V. Sós，Colloquia Mathematica Societatis János Bolyai，卷。 10 (North-Holland, 1973), pp. 585–595] 并在 Sauer 的工作中达到顶峰 [Rado 图的着色子图，Combinatorica 26(2) (2006) 231–253] 和 Laflamme–Sauer–Vuksanovic [通用结构的规范划分，Combinatorica 26(2) (2006) 183–205]，[公式：见正文]的拉姆齐理论仅进展到顶点着色的界限[P.183-205]。 Komjáth 和 V. Rödl，通用图的着色，Graphs Combin。 2(1) (1986) 55–60] 和边缘着色 [N. Sauer，可数三角形自由齐次图的边划分，离散数学。 185（1-3）（1998）137-181]。这是由于缺乏大规模技术造成的。我们通常解决这个问题：对于每个有限的无三角形图[公式：参见文本]，存在有限数量的[公式：参见文本]，使得对于将[公式：参见文本]中的[公式：参见文本]的所有副本着色为有限多种颜色，存在一个[公式：参见文本]的子图，该子图又是通用齐次无三角形的，其中着色不超过[公式：参见文本]颜色。这是省略某些非平凡有限结构副本的同质结构的第一个此类结果。该证明需要新的大规模技术的发展，包括构建编码[公式：见文本]的树的灵活方法以及拉姆齐理论的发展。
The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.