Countable Ramsey
From MaRDI portal
Publication:6394136
arXiv2203.10396MaRDI QIDQ6394136FDOQ6394136
Authors: Leonardo Nagami Coregliano, M. Malliaris 
Publication date: 19 March 2022
Abstract: The celebrated ErdH{o}s-Hajnal Conjecture says that in any proper hereditary class of finite graphs we are guaranteed to have a clique or anti-clique of size , which is a much better bound than the logarithmic size that is provided by Ramsey's Theorem in general. On the other hand, in uncountable cardinalities, the model-theoretic property of stability guarantees a uniform set much larger than the bound provided by the ErdH{o}s-Rado Theorem in general. Even though the consequences of stability in the finite have been much studied in the literature, the countable setting seems a priori quite different, namely, in the countably infinite the notion of largeness based on cardinality alone does not reveal any structure as Ramsey's Theorem already provides a countably infinite uniform set in general. In this paper, we show that the natural notion of largeness given by upper density reveals that these phenomena meet in the countable: a countable graph has an almost clique or anti-clique of positive upper density if and only if it has a positive upper density almost stable set. Moreover, this result also extends naturally to countable models of a universal theory in a finite relational language. Our methods explore a connection with the notion of convergence in the theory of limits of dense combinatorial objects, introducing and studying a natural approximate version of the ErdH{o}s-Hajnal property that allows for a negligible error in the edges (in general, predicates) but requires linear-sized uniform sets in convergent sequences of models (this is much stronger than what stable regularity can provide as the error is required to go to zero). Finally, surprisingly, we completely characterize all hereditary classes of finite graphs that have this approximate ErdH{o}s-Hajnal property. The proof highlights both differences and similarities with the original conjecture.
Combinatorial probability (60C05) Classification theory, stability, and related concepts in model theory (03C45) Ramsey theory (05D10) Measures and integrals in product spaces (28A35) Ultraproducts and related constructions (03C20)
This page was built for publication: Countable Ramsey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6394136)
