The Ramsey theory of the universal homogeneous triangle-free graph

Journal of Mathematical Logic 20 (2):2050012 (2020)
  Copy   BIBTEX

Abstract

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 H3, 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.I, 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, Combinatorica26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica26(2) (2006) 183–205], the Ramsey theory of H3 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 G, there is a finite number T(G) such that for any coloring of all copies of G in H3 into finitely many colors, there is a subgraph of H3 which is again universal homogeneous triangle-free in which the coloring takes no more than T(G) 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 H3 and the development of their Ramsey theory.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Ramsey Theory for Countable Binary Homogeneous Structures.Jean A. Larson - 2005 - Notre Dame Journal of Formal Logic 46 (3):335-352.
Small universal families for graphs omitting cliques without GCH.Katherine Thompson - 2010 - Archive for Mathematical Logic 49 (7-8):799-811.
Where are particulars and universals?Fraser MacBride - 1998 - Dialectica 52 (3):203–227.
$triangle^1_3$-Sets of Reals.Haim Judah & Saharon Shelah - 1993 - Journal of Symbolic Logic 58 (1):72-80.
Ramsey classes of topological and metric spaces.Jaroslav Nešetřil - 2006 - Annals of Pure and Applied Logic 143 (1-3):147-154.
Homogeneity in relatively free groups.Oleg Belegradek - 2012 - Archive for Mathematical Logic 51 (7-8):781-787.
The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
Logical aspects of Cayley-graphs: the group case.Dietrich Kuske & Markus Lohrey - 2004 - Annals of Pure and Applied Logic 131 (1-3):263-286.
Types in Abstract Elementary Classes.Tapani Hyttinen - 2004 - Notre Dame Journal of Formal Logic 45 (2):99-108.
$${\Pi^1_2}$$ -comprehension and the property of Ramsey.Christoph Heinatsch - 2009 - Archive for Mathematical Logic 48 (3-4):323-386.

Analytics

Added to PP
2019-12-06

Downloads
7 (#1,044,287)

6 months
1 (#448,551)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Big Ramsey degrees in universal inverse limit structures.Natasha Dobrinen & Kaiyun Wang - forthcoming - Archive for Mathematical Logic:1-33.

Add more citations

References found in this work

Models without indiscernibles.Fred G. Abramson & Leo A. Harrington - 1978 - Journal of Symbolic Logic 43 (3):572-600.
Partitions of large Rado graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
The halpern–läuchli theorem at a measurable cardinal.Natasha Dobrinen & Dan Hathaway - 2017 - Journal of Symbolic Logic 82 (4):1560-1575.

Add more references