Excluding pairs of tournaments
read the original abstract
The Erd\H{o}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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.