Excluding pairs of tournaments

The Erdos-Hajnal conjecture states that for every given undirected 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 |V(G)|^{c(H)}. The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant c(H)>0 such that every H-free tournament T contains a transitive subtournament of order at least |V(T)|^{c(H)}. We prove in this paper that {H1,H2}-free tournaments T contain transitive subtournaments of size at least |V(T)|^{c(H1,H2)} for some c(H1,H2)>0 and several pairs of tournaments: H1, H2. In particular we prove that {H,Hc}-freeness implies existence of the polynomial-size transitive subtournaments for several tournaments H for which the conjecture is still open (Hc stands for the complement of H). To the best of our knowledge these are first nontrivial results of this type.

• Algorithms and Theory