Decomposing tournaments into paths

Allan Lo; Viresh Patel; Jozef Skokan; John Talbot

Decomposing tournaments into paths

Allan Lo, Viresh Patel, Jozef Skokan, John Talbot

Mathematics

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

Abstract

We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by K\"uhn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$. There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.

Original language	English
Journal	Proceedings of the London Mathematical Society
Publication status	Accepted/In press - 29 Dec 2019

Keywords

math.CO

Cite this

@article{3226bc9b8c2045198b7fa30a2d74d476,

title = "Decomposing tournaments into paths",

abstract = " We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by K\{"}uhn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$. There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them. ",

keywords = "math.CO",

author = "Allan Lo and Viresh Patel and Jozef Skokan and John Talbot",

year = "2019",

month = dec,

day = "29",

language = "English",

journal = "Proceedings of the London Mathematical Society",

issn = "0024-6115",

publisher = "London Mathematical Society",

}

TY - JOUR

T1 - Decomposing tournaments into paths

AU - Lo, Allan

AU - Patel, Viresh

AU - Skokan, Jozef

AU - Talbot, John

PY - 2019/12/29

Y1 - 2019/12/29

N2 - We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by K\"uhn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$. There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.

AB - We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by K\"uhn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$. There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.

KW - math.CO

M3 - Article

SN - 0024-6115

JO - Proceedings of the London Mathematical Society

JF - Proceedings of the London Mathematical Society

ER -

Decomposing tournaments into paths

Abstract

Keywords

Fingerprint

Cite this