Excluding pairs of tournaments

Abstract

The Erdős-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 $\{H_1,H_2\}$-free tournaments $T$ contain transitive subtournaments of size at least $|V(T){|}^{c(H_1,H_2)}$ for some $c(H_1,H_2)>0$ and several pairs of tournaments: $H_1$, $H_2$. In particular we prove that $\{H,H^c\}$-freeness implies existence of the polynomial-size transitive subtournaments for several tournaments $H$ for which the conjecture is still open ($H^c$ stands for the \textit{complement of $H$}). To the best of our knowledge these are first nontrivial results of this type.