Path decompositions of tournaments

Antonio Jose Ferra Gomes De Almeida Girao; Bertille Granet; Daniela Kuhn; Allan Lo; Deryk Osthus

doi:10.1112/plms.12480

Path decompositions of tournaments

Antonio Jose Ferra Gomes De Almeida Girao, Bertille Granet, Daniela Kuhn^*, Allan Lo, Deryk Osthus

^*Corresponding author for this work

Mathematics

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

203 Downloads (Pure)

Abstract

In 1976, Alspach, Mason, and Pullman conjectured that any tournament 𝑇of even order can be decomposed into exactly ex(𝑇)paths, where ex(𝑇)∶=12∑𝑣∈𝑉(𝑇)|𝑑+𝑇(𝑣) −𝑑−𝑇(𝑣)|. We prove this conjecture for all sufficiently large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.

Original language	English
Journal	Proceedings of the London Mathematical Society
Early online date	19 Jan 2023
DOIs	https://doi.org/10.1112/plms.12480
Publication status	E-pub ahead of print - 19 Jan 2023

Bibliographical note

Funding Information:
We thank the referee for helpful suggestions. This project has received partial funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 786198, D. Kühn and D. Osthus). The research leading to these results was also partially supported by the EPSRC, grant nos. EP/N019504/1 (A. Girão and D. Kühn) and EP/S00100X/1 (D. Osthus).

Publisher Copyright:
© 2022 The Authors. Proceedings of the London Mathematical Society is copyright © London Mathematical Society.

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1112/plms.12480Licence: Creative Commons: Attribution (CC BY)

GirãoA2023PathFinal published version, 1.15 MBLicence: Creative Commons: Attribution (CC BY)

H2020_ERC_EXTCOMB
Osthus, D. (Co-Investigator) & Kuhn, D. (Principal Investigator)
European Commission
1/01/19 → 31/12/24
Project: EU
Approximate Structure in Large Graphs and Hypergraphs
Osthus, D. (Principal Investigator)
Engineering & Physical Science Research Council
1/01/19 → 31/12/21
Project: Research Councils
Combinatorics, Probability and Algorithms: Fellowship, Establish Career: Professor D Kuhn
Kuhn, D. (Principal Investigator)
Engineering & Physical Science Research Council
1/09/16 → 31/08/21
Project: Research Councils

Cite this

@article{0f20f7b391a748f491a03949fe688d4e,

title = "Path decompositions of tournaments",

abstract = "In 1976, Alspach, Mason, and Pullman conjectured that any tournament 푇of even order can be decomposed into exactly ex(푇)paths, where ex(푇)∶=12∑푣∈푉(푇)|푑+푇(푣) −푑−푇(푣)|. We prove this conjecture for all sufficiently large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.",

author = "{Ferra Gomes De Almeida Girao}, {Antonio Jose} and Bertille Granet and Daniela Kuhn and Allan Lo and Deryk Osthus",

note = "Funding Information: We thank the referee for helpful suggestions. This project has received partial funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 786198, D. K{\"u}hn and D. Osthus). The research leading to these results was also partially supported by the EPSRC, grant nos. EP/N019504/1 (A. Gir{\~a}o and D. K{\"u}hn) and EP/S00100X/1 (D. Osthus). Publisher Copyright: {\textcopyright} 2022 The Authors. Proceedings of the London Mathematical Society is copyright {\textcopyright} London Mathematical Society.",

year = "2023",

month = jan,

day = "19",

doi = "10.1112/plms.12480",

language = "English",

journal = "Proceedings of the London Mathematical Society",

issn = "0024-6115",

publisher = "London Mathematical Society",

}

TY - JOUR

T1 - Path decompositions of tournaments

AU - Ferra Gomes De Almeida Girao, Antonio Jose

AU - Granet, Bertille

AU - Kuhn, Daniela

AU - Lo, Allan

AU - Osthus, Deryk

N1 - Funding Information: We thank the referee for helpful suggestions. This project has received partial funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 786198, D. Kühn and D. Osthus). The research leading to these results was also partially supported by the EPSRC, grant nos. EP/N019504/1 (A. Girão and D. Kühn) and EP/S00100X/1 (D. Osthus). Publisher Copyright: © 2022 The Authors. Proceedings of the London Mathematical Society is copyright © London Mathematical Society.

PY - 2023/1/19

Y1 - 2023/1/19

N2 - In 1976, Alspach, Mason, and Pullman conjectured that any tournament 푇of even order can be decomposed into exactly ex(푇)paths, where ex(푇)∶=12∑푣∈푉(푇)|푑+푇(푣) −푑−푇(푣)|. We prove this conjecture for all sufficiently large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.

AB - In 1976, Alspach, Mason, and Pullman conjectured that any tournament 푇of even order can be decomposed into exactly ex(푇)paths, where ex(푇)∶=12∑푣∈푉(푇)|푑+푇(푣) −푑−푇(푣)|. We prove this conjecture for all sufficiently large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.

UR - http://www.scopus.com/inward/record.url?scp=85146450935&partnerID=8YFLogxK

U2 - 10.1112/plms.12480

DO - 10.1112/plms.12480

M3 - Article

AN - SCOPUS:85146450935

SN - 0024-6115

JO - Proceedings of the London Mathematical Society

JF - Proceedings of the London Mathematical Society

ER -

Path decompositions of tournaments

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

H2020_ERC_EXTCOMB

Approximate Structure in Large Graphs and Hypergraphs

Combinatorics, Probability and Algorithms: Fellowship, Establish Career: Professor D Kuhn

Cite this