Seminars & Colloquia Calendar

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. However, in the case of countable structures balanced between these two, all structures seem to behave in the same way since the infinite version of Ramsey's Theorem already yields a uniform set of the maximum possible cardinality.
By instead considering a different notion of large sets, namely, that of positive upper density and ignoring negligible errors, we show that the same phenomenon happens in the countable: a countable graph has a large almost clique or a large almost anti-clique if and only if it has a large almost stable set. Similarly, in the countable we can consider a variant Erd?s-Hajnal property: we say that a hereditary class of finite graphs \(C\) has the approximate Erd?s-Hajnal property (AEHP) if every countable graph whose finite induced subgraphs are all in \(C\) must contain a large almost clique or a large almost anti-clique. Surprisingly, AEHP has a simple characterization as precisely those classes that avoid some recursive blow-up of the 4-cycle.
In this talk, I will explain how these problems are reduced to problems for limits of dense graph sequences (graphons) and show how the corresponding graphon problems have very clean combinatorial proofs. No background knowledge in model theory or in the theory of graphons will be required.
This talk is based on joint work with Maryanthe Malliaris.