The Erdos-Hajnal Conjecture for a new infinite class of tournaments

Krzysztof Choromanski

Columbia University

Abstract

The Erdos-Hajnal Conjecture states that for every given graph H there exists a constant c(H)>0 such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size at least |G|^{c(H)}. The conjecture is still open. However some time ago its directed version was proven to be equivalent to the original one. In the directed version graphs are replaced by tournaments, and cliques and stable sets by transitive subtournaments. Both the directed and the undirected versions of the conjecture are known to be true for small graphs (or tournaments), and there are operations allowing to build bigger graphs (or tournaments) for which the conjecture holds. We were able to prove the conjecture for an infinite class of tournaments that is not obtained in the way described above. To the best of our knowledge, this is the first result of this kind.