Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Stephen Gould; Tom Kelly; Daniela Kuhn; Deryk Osthus

doi:10.1016/j.jctb.2022.04.003

Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Stephen Gould, Tom Kelly, Daniela Kuhn, Deryk Osthus

Mathematics

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

37 Downloads (Pure)

Abstract

A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of K_n admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of K_nadmit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of K_nand answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.

Original language	English
Pages (from-to)	57-100
Number of pages	44
Journal	Journal of Combinatorial Theory. Series B
Volume	156
Early online date	3 May 2022
DOIs	https://doi.org/10.1016/j.jctb.2022.04.003
Publication status	Published - Sept 2022

Bibliographical note

Funding Information:
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 (T. Kelly and D. Kühn) and EP/S00100X/1 (D. Osthus).

Publisher Copyright:
© 2022 The Author(s)

Keywords

Andersen's conjecture
Edge-colouring
Rainbow path
Rainbow cycle
Hypergraph matchings
Distributive absorption
Latin squares

Access to Document

10.1016/j.jctb.2022.04.003Licence: Creative Commons: Attribution (CC BY)

GouldS2022AlmostFinal published version, 824 KBLicence: Creative Commons: Attribution (CC BY)

1 Active
2 Finished

H2020_ERC_EXTCOMB
Osthus, D. & Kuhn, D.
European Commission
1/01/19 → 31/12/24
Project: EU
Approximate Structure in Large Graphs and Hypergraphs
Osthus, D.
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.
Engineering & Physical Science Research Council
1/09/16 → 31/08/21
Project: Research Councils

Cite this

@article{ad20c07913624d0fa4a7d1ac8150a08e,

title = "Almost all optimally coloured complete graphs contain a rainbow Hamilton path",

abstract = "A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.",

keywords = "Andersen's conjecture, Edge-colouring, Rainbow path, Rainbow cycle, Hypergraph matchings, Distributive absorption, Latin squares",

author = "Stephen Gould and Tom Kelly and Daniela Kuhn and Deryk Osthus",

note = "Funding Information: 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 (T. Kelly and D. K{\"u}hn) and EP/S00100X/1 (D. Osthus). Publisher Copyright: {\textcopyright} 2022 The Author(s)",

year = "2022",

month = sep,

doi = "10.1016/j.jctb.2022.04.003",

language = "English",

volume = "156",

pages = "57--100",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Almost all optimally coloured complete graphs contain a rainbow Hamilton path

AU - Gould, Stephen

AU - Kelly, Tom

AU - Kuhn, Daniela

AU - Osthus, Deryk

N1 - Funding Information: 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 (T. Kelly and D. Kühn) and EP/S00100X/1 (D. Osthus). Publisher Copyright: © 2022 The Author(s)

PY - 2022/9

Y1 - 2022/9

N2 - A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.

AB - A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.

KW - Andersen's conjecture

KW - Edge-colouring

KW - Rainbow path

KW - Rainbow cycle

KW - Hypergraph matchings

KW - Distributive absorption

KW - Latin squares

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

U2 - 10.1016/j.jctb.2022.04.003

DO - 10.1016/j.jctb.2022.04.003

M3 - Article

SN - 0095-8956

VL - 156

SP - 57

EP - 100

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Abstract

Bibliographical note

Keywords

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