New advances in the Erdos-Hajnal conjecture

Krzysztof Choromanski, Google Research
Fine Hall 224

The celebrated open Erdos-Hajnal conjecture states that for every undirected graph H there exists epsilon(H)>0 such that every H-free undirected n-vertex graph contains a clique or a stable set of size at least n^{epsilon(H)}. (``H-free'' means it does not contain H as an induced subgraph.) A weaker version of the conjecture states that if one excludes both H and its complement H^{c} then there is a clique or a stable set of size at least n^{epsilon(H)}. This version is also open. There is also an equivalent directed variant of the conjecture, where undirected graphs are replaced by tournaments and cliques/stable sets by transitive subtournaments. In this talk I will present some new results regarding the conjecture. In particular, I will show that the weaker version of the conjecture is satisfied if H is a tree on at most six vertices. I will also show results on excluding pairs of tournaments in the directed setting, and a proof giving tight asymptotic bounds on the so-called Erdos-Hajnal coefficient of the directed path P_{k}, for any k > 0. This proof has as a corollary a quadratic time algorithm for constructing polynomial-size transitive subsets in P_{k}-free tournaments. Finally, I will explain some recent results suggesting that if true, the conjecture is satisfied with epsilon(H) > c/|H| for some universal constant c>0. Joint work with Dvir Falik, Anita Liebenau, Viresh Pateli, and Marcin Pilipczuk.