# Excluding pairs of tournaments

### Venue

Journal of Graph Theory (JGT) (2018) (to appear)

### Publication Year

2018

### Authors

### BibTeX

## 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.