New classes of tournaments satisfying the Erdos-Hajnal Conjecture

Presented by: Krzysztof Choromanski (Columbia University & Google) This talk is about one of the most challenging open combinatorial Ramsey - type problems, the so-called Erdos-Hajnal Conjecture. I will show some very recent results concerning the Conjecture. The Erdos-Hajnal conjecture states that for every graph H there exists a constant such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size. The conjecture is still open. However some time ago a version for tournaments was proven to be equivalent to the original. In the tournament version, graphs are replaced by tournaments, and cliques and stable sets by transitive subtournaments. Both the tournament and the graph versions of the conjecture are known to be true for some small graphs (or tournaments) H, and there are operations that build bigger graphs (or tournaments) for which the conjecture holds. I will show the conjecture for an infinite class of tournaments that is not obtained in the way described above. To the best of our knowledge, this is the first result of this kind. The only five-vertex tournament for which the conjecture was open was the tournament C5 in which every vertex has outdegree two. I will show a proof that C5 satisfies the conjecture. Consequently all 5-vertex tournaments satisfy the conjecture. Finally I will talk about the tournaments that satisfy the conjecture in an "almost linear sense" (so-called pseudocelebrities). A construction of all pseudocelebrities will be given. The part of the talk about pseudocelebrities is joint work with Maria Chudnovsky (Columbia University) and Paul Seymour (Princeton University). The other part is joint work with Eli Berger (Haifa University) and Maria Chudnovsky.