The Ramsey theory of the universal homogeneous triangle-free graph

DOI10.1142/S0219061320500129zbMATH Open1485.03185arXiv1704.00220OpenAlexW3098291420MaRDI QIDQ5118053FDOQ5118053

Natasha Dobrinen

Publication date: 4 September 2020

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ramsey classes of set systems
• Partitions of finite relational and set systems
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• More on the Kechris-Pestov-Todorcevic correspondence: precompact expansions
• Models Without Indiscernibles
• A partition calculus in set theory
• Introduction to Ramsey Spaces (AM-174)
• A survey on structural Ramsey theory and topological dynamics with the Kechris-Pestov-Todorcevic correspondence in mind
• Ramsey's Theorem for n-Parameter Sets
• A Partition Theorem
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• A Ramsey theorem for trees
• A canonical partition theorem for uniform families of finite strong subtrees
• A family of countable homogeneous graphs
• A Partition Theorem for the Infinite Subtrees of a Tree
• Partition properties of the dense local order and a colored version of Milliken's theorem
• Ramsey's theorem for a class of categories
• Canonical partitions of universal structures
• Edge partitions of the countable triangle free homogeneous graph
• Products of Infinitely Many Perfect Trees
• Coloring subgraphs of the Rado graph
• Counting canonical partitions in the random graph
• Edge partitions of the Rado graph
• Partitions of large Rado graphs
• Coloring of universal graphs
• Errata to ``Ramsey's theorem for a class of categories
• A TAIL CONE VERSION OF THE HALPERN–LÄUCHLI THEOREM AT A LARGE CARDINAL
• Big Ramsey degrees and topological dynamics
• Big Ramsey Degrees and Divisibility in Classes of Ultrametric Spaces
• THE HALPERN–LÄUCHLI THEOREM AT A MEASURABLE CARDINAL

Cited In (11)

• The Ramsey theory of Henson graphs
• Dual Ramsey properties for classes of algebras
• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• 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
• A universal partition result for infinite homogeneous \(K_n\)-free and related graphs
• Big Ramsey degrees of 3-uniform hypergraphs are finite
• Big Ramsey degrees in universal inverse limit structures
• Ramsey theory of homogeneous structures: current trends and open problems
• A Ramsey theorem for countable homogeneous directed graphs

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)