Large unavoidable subtournaments

Research output: Contribution to journalArticlepeer-review

Standard

Large unavoidable subtournaments. / Long, Eoin.

In: Combinatorics, Probability and Computing, Vol. 26, No. 1, 01.01.2017, p. 68-77.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Bibtex

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

}

RIS

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

VL - 26

SP - 68

EP - 77

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 1

ER -