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: 92,991

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

The Ramsey theory of Henson graphs.Natasha Dobrinen - 2022 - Journal of Mathematical Logic 23 (1).
Ramsey Theory for Countable Binary Homogeneous Structures.Jean A. Larson - 2005 - Notre Dame Journal of Formal Logic 46 (3):335-352.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Partitions of large Rado graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Reverse Mathematics and the Coloring Number of Graphs.Matthew Jura - 2016 - Notre Dame Journal of Formal Logic 57 (1):27-44.
Small universal families for graphs omitting cliques without GCH.Katherine Thompson - 2010 - Archive for Mathematical Logic 49 (7-8):799-811.
Domatic partitions of computable graphs.Matthew Jura, Oscar Levin & Tyler Markkanen - 2014 - Archive for Mathematical Logic 53 (1-2):137-155.
Twilight graphs.J. C. E. Dekker - 1981 - Journal of Symbolic Logic 46 (3):539-571.
Big Ramsey degrees in universal inverse limit structures.Natasha Dobrinen & Kaiyun Wang - 2023 - Archive for Mathematical Logic 62 (3):471-503.

Analytics

Added to PP
2019-12-06

Downloads
21 (#761,575)

6 months
11 (#272,549)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Ramsey theory of Henson graphs.Natasha Dobrinen - 2022 - Journal of Mathematical Logic 23 (1).
Forcing with copies of the Rado and Henson graphs.Osvaldo Guzmán & Stevo Todorcevic - 2023 - Annals of Pure and Applied Logic 174 (8):103286.
Big Ramsey degrees in universal inverse limit structures.Natasha Dobrinen & Kaiyun Wang - 2023 - Archive for Mathematical Logic 62 (3):471-503.

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