### Abstract

Let H be a tournament, and let ε≥0 be a real number. We call ε an "Erdos-Hajnal coefficient" for H if there exists c>0 such that in every tournament G not containing H as a subtournament, there is a transitive subset of cardinality at least c|V(G)|^{ε}. The Erdos-Hajnal conjecture asserts, in one form, that every tournament H has a positive Erdos-Hajnal coefficient. This remains open, but recently the tournaments with Erdos-Hajnal coefficient 1 were completely characterized. In this paper we provide an analogous theorem for tournaments that have an Erdos-Hajnal coefficient larger than 5/6; we give a construction for them all, and we prove that for any such tournament H there are numbers c, d such that, if a tournament G with |V(G)|>1 does not contain H as a subtournament, then V(G) can be partitioned into at most c(log(|V(G)|))^{d} transitive subsets.

Original language | English (US) |
---|---|

Pages (from-to) | 228-249 |

Number of pages | 22 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 109 |

DOIs | |

State | Published - Nov 1 2014 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- The erdos-hajnal conjecture
- Tournaments

## Fingerprint Dive into the research topics of 'Tournaments with near-linear transitive subsets'. Together they form a unique fingerprint.

## Cite this

*Journal of Combinatorial Theory. Series B*,

*109*, 228-249. https://doi.org/10.1016/j.jctb.2014.06.007