The Ramsey theory of the universal homogeneous triangle-free graph

Abstract

The universal homogeneous triangle-free graph, constructed by Henson and denoted ${\mathcal{H}}_3$, 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á and culminating in work of Sauer and Laflamme-Sauer-Vuksanovic, the Ramsey theory of ${\mathcal{H}}_3$ had only progressed to bounds for vertex colorings (Komjáth-Rödl) and edge colorings (Sauer). 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 ${\mathcal{H}}_3$ into finitely many colors, there is a subgraph of ${\mathcal{H}}_3$ 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 non-trivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code ${\mathcal{H}}_3$ and the development of their Ramsey theory.

Accepted to Journal of Mathematical Logic. 65 pages. A few references updated

References in corpus (1)

• A tail cone version of the Halpern-Läuchli theorem at a large cardinal

Cited by in corpus (3)

• Big Ramsey degrees using parameter spaces
• Twenty years of Nešetřil's classification programme of Ramsey classes
• Big Ramsey Degrees of Countable Ordinals