2149. Leonardo N. Coregliano, Maryanthe Malliaris Countable Ramsey
E-mail:
Submission date: 19 March 2022
Abstract:
The celebrated Erdő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 n^c, 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 Erdő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 Erdő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 Erdős-Hajnal
property.
The proof highlights both differences and similarities with the original
conjecture.