The Ramsey theory of Henson graphs

Journal of Mathematical Logic (forthcoming)
  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 [Formula: see text]-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: 76,140

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

Forking and Dividing in Henson Graphs.Gabriel Conant - 2017 - Notre Dame Journal of Formal Logic 58 (4):555-566.
Reverse mathematics and infinite traceable graphs.Peter Cholak, David Galvin & Reed Solomon - 2012 - Mathematical Logic Quarterly 58 (1-2):18-28.
Reducts of the Henson graphs with a constant.András Pongrácz - 2017 - Annals of Pure and Applied Logic 168 (7):1472-1489.
Peirce's Logical Graphs for Boolean Algebras and Distributive Lattices.Minghui Ma - 2018 - Transactions of the Charles S. Peirce Society 54 (3):320.
Ramsey sentences for infinite theories.Herbert E. Hendry - 1975 - Philosophy of Science 42 (1):28.
Did Ramsey ever endorse a redundancy theory of truth?María J. Frápolli - 2011 - Tópicos: Revista de Filosofía 41 (1):315-332.
Some coinductive graphs.A. H. Lachlan - 1990 - Archive for Mathematical Logic 29 (4):213-229.

Analytics

Added to PP
2022-06-19

Downloads
2 (#1,400,884)

6 months
1 (#447,993)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Big Ramsey degrees in universal inverse limit structures.Natasha Dobrinen & Kaiyun Wang - forthcoming - Archive for Mathematical Logic:1-33.

Add more citations

References found in this work

No references found.

Add more references