Google Research

Excluding pairs of tournaments

Journal of Graph Theory (JGT) (2018)

Abstract

The Erdos-Hajnal conjecture states that for every given undirected graph H there exists a constant c(H)>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 |V(G)|^{c(H)}. The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant c(H)>0 such that every H-free tournament T contains a transitive subtournament of order at least |V(T)|^{c(H)}. We prove in this paper that {H1,H2}-free tournaments T contain transitive subtournaments of size at least |V(T)|^{c(H1,H2)} for some c(H1,H2)>0 and several pairs of tournaments: H1, H2. In particular we prove that {H,Hc}-freeness implies existence of the polynomial-size transitive subtournaments for several tournaments H for which the conjecture is still open (Hc stands for the complement of H). To the best of our knowledge these are first nontrivial results of this type.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work