Large unavoidable subtournaments

Eoin Long

doi:10.1017/S0963548316000213

Large unavoidable subtournaments

Eoin Long

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Let D_k denote the tournament on 3k vertices consisting of three disjoint vertex classes V₁, V₂ and V₃ of size k, each oriented as a transitive subtournament, and with edges directed from V₁ to V₂, from V₂ to V₃ and from V₃ to V₁. Fox and Sudakov proved that given a natural number k and ε > 0, there is n₀(k, ε) such that every tournament of order n ⩾ n₀(k,ε) which is ε-far from being transitive contains D_k as a subtournament. Their proof showed that and they conjectured that this could be reduced to n₀(k, ε) ⩽ ε^−O(k). Here we prove this conjecture.

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
DOIs	https://doi.org/10.1017/S0963548316000213
Publication status	Published - 1 Jan 2017

Keywords

Tournaments
Ramsey theory

Access to Document

10.1017/S0963548316000213Licence: None: All rights reserved

Cite this

@article{987e2174a2a74c6c94af77f2fd6bb2f9,

title = "Large unavoidable subtournaments",

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.",

keywords = "Tournaments, Ramsey theory",

author = "Eoin Long",

year = "2017",

month = jan,

day = "1",

doi = "10.1017/S0963548316000213",

language = "English",

volume = "26",

pages = "68--77",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "1",

}

TY - JOUR

T1 - Large unavoidable subtournaments

AU - Long, Eoin

PY - 2017/1/1

Y1 - 2017/1/1

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

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

KW - Tournaments

KW - Ramsey theory

U2 - 10.1017/S0963548316000213

DO - 10.1017/S0963548316000213

M3 - Article

SN - 0963-5483

VL - 26

SP - 68

EP - 77

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 1

ER -

Large unavoidable subtournaments

Abstract

Keywords

Access to Document

Fingerprint

Cite this