Path decompositions of tournaments

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

*Corresponding author for this work

Research output: Contribution to journal β€Ί Article β€Ί peer-review

82 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 languageEnglish
JournalProceedings of the London Mathematical Society
Early online date19 Jan 2023
DOIs
Publication statusE-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

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Path decompositions of tournaments'. Together they form a unique fingerprint.

Cite this