# The near-Erdős–Hajnal property of some prime graphs

# The near-Erdős–Hajnal property of some prime graphs

Erdős and Hajnal conjectured that for every graph H, there exists c>0 such that every graph on n vertices with no induced copy of H contains a clique or a stable set of size at least n^c. Alon, Pach, and Solymosi reduced this conjecture to the case when H is prime, or equivalently when H cannot be obtained by blowing up smaller graphs. But so far, it has not been shown for any prime graph with more than five vertices. This talk describes a construction of infinitely many prime graphs that each "almost" satisfies the Erdős–Hajnal conjecture. More exactly, for every such graph H, every graph on n vertices with no induced copy of H contains a clique or a stable set of size at least 2^{(log n)^{1-o(1)}}. The proof method actually gives the stronger result that each such graph H has the "near-polynomial Rödl–Nikiforov" property, which will be explained in the talk.