The Erdos-Hajnal conjecture states that for every graph $H$ there exists a constant $c>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 $|G|^c$. 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 wasthe tournament $C_5$ in which every vertex has outdegree two. I will show a proof that $C_5$ 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 and Paul Seymour. The other part is joint work with Eli Berger and Maria Chudnovsky.