Forbidding Couples of Tournaments and the Erdös-Hajnal Conjecture

Abstract

A celebrated unresolved conjecture of Erdös and Hajnal states that for every undirected graph $H$ there exists $\epsilon (H)>0$ such that every undirected graph on $n$ vertices that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $n^{\epsilon (H)}$. This conjecture has a directed equivalent version stating that for every tournament $H$ there exists $\epsilon (H)>0$ such that every $H-$free $n-$vertex tournament $T$ contains a transitive subtournament of size at least $n^{\epsilon (H)}$. Recently the conjecture was proved for all six-vertex tournaments, except $K_6$. In this paper we construct two infinite families of tournaments for which the conjecture is still open for infinitely many tournaments in these two families $-$ the family of so-called super nebulas and the family of so-called super triangular galaxies. We prove that for every super nebula $H_1$ and every $\Delta$galaxy $H_2$ there exist $\epsilon (H_1,H_2)$ such that every $\{H_1,H_2\}$$-$free tournament $T$ contains a transitive subtournament of size at least $\mid$$T$${\mid }^{\epsilon (H_1,H_2)}$. We also prove that for every central triangular galaxy $H$ there exist $\epsilon (K_6,H)$ such that every $\{K_6,H\}$$-$free tournament $T$ contains a transitive subtournament of size at least $\mid$$T$${\mid }^{\epsilon (K_6,H)}$. And we give an extension of our results.

arXiv commentarXiv admin note: text overlap with arXiv:2010.12329