Large unavoidable subtournaments

Research output: Contribution to journalArticlepeer-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 languageEnglish
Pages (from-to)68-77
Number of pages10
JournalCombinatorics, Probability and Computing
Volume26
Issue number1
Early online date21 Jun 2016
Publication statusPublished - 1 Jan 2017

Keywords

  • Tournaments, Ramsey theory