Large unavoidable subtournaments
Research output: Contribution to journal › Article › peer-review
Authors
Colleges, School and Institutes
Abstract
Let Dk denote the tournament on 3k vertices consisting of three disjoint vertex classes V1, V2 and V3 of size k, each oriented as a transitive subtournament, and with edges directed from V1 to V2, from V2 to V3 and from V3 to V1. Fox and Sudakov proved that given a natural number k and ε > 0, there is n0(k, ε) such that every tournament of order n ⩾ n0(k,ε) which is ε-far from being transitive contains Dk as a subtournament. Their proof showed that and they conjectured that this could be reduced to n0(k, ε) ⩽ ε−O(k). Here we prove this conjecture.
Details
Original language | English |
---|---|
Pages (from-to) | 68-77 |
Number of pages | 10 |
Journal | Combinatorics, Probability and Computing |
Volume | 26 |
Issue number | 1 |
Early online date | 21 Jun 2016 |
Publication status | Published - 1 Jan 2017 |
Keywords
- Tournaments, Ramsey theory