The universal triangle-free graph has finite big Ramsey degrees

Natasha Dobrinen

Published 2017-04-01Version 1

The universal homogeneous triangle-free graph $\mathcal{H}_3$ has finite `big Ramsey degrees': For each finite triangle-free graph $G$, there is a finite number $n(G)$ such that for any coloring $c$ of all copies of $G$ in $\mathcal{H}_3$ into finitely many colors, there is a subgraph $\mathcal{H}'$ of $\mathcal{H}_3$ which is isomorphic to $\mathcal{H}_3$ in which $c$ takes on no more than $n(G)$ many colors. The proof hinges on the following developments: a new flexible method for constructing trees which code the universal triangle-free graph, called strong coding trees; a new notion of isomorphism type of finite subtrees of a strong coding tree; analogues of the Halpern-L\"{a}uchli and Milliken Theorems, obtaining a Ramsey theorem for strict similarity types of finite subtrees of a given strong coding tree; and new notions of subtree envelope. The proof of the analogue of the Halpern-L\"{a}uchli theorem for strong coding trees uses forcing techniques, though the proof is in ZFC, building on ideas from Harrington's proof of the Halpern-L\"{a}uchli Theorem.