The Ramsey theory of Henson graphs

Journal of Mathematical Logic 23 (1) (2022)
  Copy   BIBTEX

Abstract

Analogues of Ramsey’s Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors in an isomorphic substructure rather than one color, as that is often impossible. Such theorems for Henson graphs however remained elusive, due to lack of techniques for handling forbidden cliques. Building on the author’s recent result for the triangle-free Henson graph, we prove that for each [Formula: see text], the k-clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramsey’s Theorem. We develop a method for coding copies of Henson graphs into a new class of trees, called strong coding trees, and prove Ramsey theorems for these trees which are applied to deduce finite big Ramsey degrees. The approach here provides a general methodology opening further study of big Ramsey degrees for ultrahomogeneous structures. The results have bearing on topological dynamics via work of Kechris, Pestov, and Todorcevic and of Zucker.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,745

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

Big Ramsey degrees in universal inverse limit structures.Natasha Dobrinen & Kaiyun Wang - 2023 - Archive for Mathematical Logic 62 (3):471-503.
Forking and Dividing in Henson Graphs.Gabriel Conant - 2017 - Notre Dame Journal of Formal Logic 58 (4):555-566.
Ramsey Theory for Countable Binary Homogeneous Structures.Jean A. Larson - 2005 - Notre Dame Journal of Formal Logic 46 (3):335-352.
Indiscernibles, EM-Types, and Ramsey Classes of Trees.Lynn Scow - 2015 - Notre Dame Journal of Formal Logic 56 (3):429-447.
The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
Ramsey’s coheirs.Eugenio Colla & Domenico Zambella - 2022 - Journal of Symbolic Logic 87 (1):377-391.

Analytics

Added to PP
2022-06-19

Downloads
16 (#227,957)

6 months
11 (#1,140,922)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

A new proof that analytic sets are Ramsey.Erik Ellentuck - 1974 - Journal of Symbolic Logic 39 (1):163-165.
Borel sets and Ramsey's theorem.Fred Galvin & Karel Prikry - 1973 - Journal of Symbolic Logic 38 (2):193-198.
Models without indiscernibles.Fred G. Abramson & Leo A. Harrington - 1978 - Journal of Symbolic Logic 43 (3):572-600.

View all 8 references / Add more references