EH-suprema of tournaments with no nontrivial homogeneous sets.

A celebrated unresolved conjecture of Erdös and Hajnal states that for every undirected graph H there exists ϵ ( 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 ϵ ( H ) . The conjecture has directed equivalent version stating that for every tournament H there exists ϵ ( H ) > 0 such that every H -free n -vertex tournament T contains a transitive subtournament of order at least n ϵ ( H ) . For a fixed tournament H , define ξ ( H ) to be the supremum of all ϵ for which the following holds: for some n 0 and every n > n 0 every tournament with n ≥ n 0 vertices not containing H as a subtournament has a transitive subtournament of size at least n ϵ . We call ξ ( H ) the EH-supremum of H . The Erdös–Hajnal conjecture is true if and only if ξ ( H ) > 0 for every H . If the conjecture is false then the smallest counterexample has no nontrivial so-called homogeneous sets (to be defined below). Therefore of interest are EH-suprema of those tournaments. In [5] it was proven that there exists a constant η > 0 such that ξ ( H ) ≤ 4 h ( 1 + η log ⁡ ( h ) h ) for almost every h -vertex tournament H . However this result does not say anything about ξ ( H ) for an arbitrarily chosen tournament with no nontrivial homogeneous sets. We address that problem in this paper, proving that there exists C > 0 such that every h -vertex tournament H with no nontrivial homogeneous sets satisfies ξ ( H ) ≤ C log ⁡ ( h ) h . We will also give upper bounds on sizes of families of h -vertex tournaments with big EH-suprema. In [1] Alon, Pach and Solymosi proposed a procedure that produces bigger graphs satisfying the conjecture from smaller ones. All graphs obtained in such a way have nontrivial homogeneous sets. For a long time that was the only method to obtain infinite families of graphs satisfying the conjecture. Recently Berger, the author and Chudnovsky (see [2] ) constructed a new infinite family of tournaments (so-called galaxies , to be defined below) that satisfies the conjecture and with no nontrivial homogeneous sets. Therefore it cannot be obtained by the procedure described in [1] . In this paper we construct a new infinite family of tournaments satisfying the conjecture – the family of so-called constellations (to be defined below). These results extend the results of [2] since every galaxy is a constellation. [ABSTRACT FROM AUTHOR]