The Ramsey theory of the universal homogeneous triangle-free graph

DOI10.1142/S0219061320500129MaRDI QIDQ5118053zbMATH OpenOpenAlexFDO

Authors Natasha Dobrinen

Publication date 4 September 2020

Published in Journal of Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.00220

zbMATH Keywords

treesRamsey theoryuniversal homogenous triangle-free graph

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Partition relations (03E02) Ramsey theory (05D10) Applications of set theory (03E75)

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 ErdH{o}s-Hajnal-Pos'{a} 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'{a}th-R"{o}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.

Recommendations

• The Ramsey theory of Henson graphs
• Edge partitions of the countable triangle free homogeneous graph
• Coloring of universal graphs
• Chromatic Ramsey theory
• On the structure of triangle-free graphs of large minimum degree

Cites work

• scientific article; zbMATH DE number 3487493 (Why is no real title available?)
• scientific article; zbMATH DE number 1229876 (Why is no real title available?)
• scientific article; zbMATH DE number 3368622 (Why is no real title available?)
• A Partition Theorem
• A Partition Theorem for the Infinite Subtrees of a Tree
• A Ramsey theorem for trees
• A canonical partition theorem for uniform families of finite strong subtrees
• A family of countable homogeneous graphs
• A partition calculus in set theory
• A survey on structural Ramsey theory and topological dynamics with the Kechris-Pestov-Todorcevic correspondence in mind
• A tail cone version of the Halpern-Läuchli theorem at a large cardinal
• Big Ramsey Degrees and Divisibility in Classes of Ultrametric Spaces
• Big Ramsey degrees and topological dynamics
• Canonical partitions of universal structures
• Coloring of universal graphs
• Coloring subgraphs of the Rado graph
• Counting canonical partitions in the random graph
• Edge partitions of the Rado graph
• Edge partitions of the countable triangle free homogeneous graph
• Errata to ``Ramsey's theorem for a class of categories
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• Introduction to Ramsey space
• Models Without Indiscernibles
• More on the Kechris-Pestov-Todorcevic correspondence: precompact expansions
• Partition properties of the dense local order and a colored version of Milliken's theorem
• Partitions of finite relational and set systems
• Partitions of large Rado graphs
• Products of Infinitely Many Perfect Trees
• Ramsey classes of set systems
• Ramsey's Theorem for n-Parameter Sets
• Ramsey's theorem for a class of categories
• Some applications of the method of forcing
• The Halpern-Läuchli theorem at a measurable cardinal

Cited in

(13)

• Dual Ramsey properties for classes of algebras
• Ramsey theory on infinite structures and the method of strong coding trees
• The Ramsey theory of Henson graphs
• Big Ramsey degrees of 3-uniform hypergraphs are finite
• Forcing with copies of the Rado and Henson graphs
• On big Ramsey degrees for binary free amalgamation classes
• Carlson-Simpson's lemma and applications in reverse mathematics
• Big Ramsey degrees in universal inverse limit structures
• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• A universal partition result for infinite homogeneous \(K_n\)-free and related graphs
• Ramsey theory of homogeneous structures: current trends and open problems
• A Ramsey theorem for countable homogeneous directed graphs
• Edge partitions of the countable triangle free homogeneous graph

This page was built for publication: The Ramsey theory of the universal homogeneous triangle-free graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5118053)