A proof of Sumner's universal tournament conjecture for large tournaments

Daniela Kuhn; Richard Mycroft; Deryk Osthus

doi:10.1112/plms/pdq035

A proof of Sumner's universal tournament conjecture for large tournaments

Daniela Kuhn, Richard Mycroft, Deryk Osthus

Mathematics

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

16 Citations (Scopus)

Abstract

Sumner's universal tournament conjecture states that any tournament on 2n - 2 vertices contains any directed tree on n vertices. In this paper we prove that this conjecture holds for all sufficiently large n. The proof makes extensive use of results and ideas from a recent paper by the same authors, in which an approximate version of the conjecture was proved.

Original language	English
Pages (from-to)	731-766
Number of pages	36
Journal	London Mathematical Society. Proceedings
Volume	102
DOIs	https://doi.org/10.1112/plms/pdq035
Publication status	Published - 1 Apr 2011

Access to Document

10.1112/plms/pdq035

Directed graphs and the regularity method
Kuhn, D. & Osthus, D.
Engineering & Physical Science Research Council
1/10/07 → 31/03/11
Project: Research Councils

Cite this

@article{3ad27d6e32054990b69ed3ade6bea03b,

title = "A proof of Sumner's universal tournament conjecture for large tournaments",

abstract = "Sumner's universal tournament conjecture states that any tournament on 2n - 2 vertices contains any directed tree on n vertices. In this paper we prove that this conjecture holds for all sufficiently large n. The proof makes extensive use of results and ideas from a recent paper by the same authors, in which an approximate version of the conjecture was proved.",

author = "Daniela Kuhn and Richard Mycroft and Deryk Osthus",

year = "2011",

month = apr,

day = "1",

doi = "10.1112/plms/pdq035",

language = "English",

volume = "102",

pages = "731--766",

journal = "London Mathematical Society. Proceedings ",

issn = "1460-244X",

publisher = "London Mathematical Society",

}

TY - JOUR

T1 - A proof of Sumner's universal tournament conjecture for large tournaments

AU - Kuhn, Daniela

AU - Mycroft, Richard

AU - Osthus, Deryk

PY - 2011/4/1

Y1 - 2011/4/1

N2 - Sumner's universal tournament conjecture states that any tournament on 2n - 2 vertices contains any directed tree on n vertices. In this paper we prove that this conjecture holds for all sufficiently large n. The proof makes extensive use of results and ideas from a recent paper by the same authors, in which an approximate version of the conjecture was proved.

AB - Sumner's universal tournament conjecture states that any tournament on 2n - 2 vertices contains any directed tree on n vertices. In this paper we prove that this conjecture holds for all sufficiently large n. The proof makes extensive use of results and ideas from a recent paper by the same authors, in which an approximate version of the conjecture was proved.

U2 - 10.1112/plms/pdq035

DO - 10.1112/plms/pdq035

M3 - Article

SN - 1460-244X

VL - 102

SP - 731

EP - 766

JO - London Mathematical Society. Proceedings

JF - London Mathematical Society. Proceedings

ER -

A proof of Sumner's universal tournament conjecture for large tournaments

Abstract

Access to Document

Fingerprint

Projects

Directed graphs and the regularity method

Cite this