ÍâÍøÌìÌÃ

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.