A celebrated unresolved conjecture of Erd\H{ o}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 stable set of size at least $n^{ \epsilon(H)}$. The 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 order at least $n^{ \epsilon(H)}$. We say that a tournament is \textit{ prime} if it does not have nontrivial homogeneous sets. So far the conjecture was proved only for some specific families of prime tournaments (\cite{ chorochudber, choromanski2}) and tournaments constructed according to the so-called \textit{ substitution procedure}(\cite{ alon}). In particular, recently the conjecture was proved for all five-vertex tournaments (\cite{ chorochudber}), but the question about the correctness of the conjecture for all six-vertex tournaments remained open. In this paper we prove that all but at most one six-vertex tournament satisfy the Erd\H{ o}s-Hajnal conjecture. That reduces the six-vertex case to a single tournament.
Categories: math.CO
