TY - JOUR

T1 - Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles

AU - Alon, Noga

AU - Pokrovskiy, Alexey

AU - Sudakov, Benny

N1 - Funding Information:
Research supported in part by a USA-Israeli BSF grant 2012/107, by an ISF grant 620/13 and by the Israeli I-Core program. Research supported in part by SNSF grant 200021-149111.
Publisher Copyright:
© 2017, Hebrew University of Jerusalem.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. In 1980 Hahn conjectured that every properly edge-coloured complete graph Kn has a rainbow Hamiltonian path. Although this conjecture turned out to be false, it was widely believed that such a colouring always contains a rainbow cycle of length almost n. In this paper, improving on several earlier results, we confirm this by proving that every properly edge-coloured Kn has a rainbow cycle of length n − O(n3/4). One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured Kn formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular, it has very good expansion properties.

AB - A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. In 1980 Hahn conjectured that every properly edge-coloured complete graph Kn has a rainbow Hamiltonian path. Although this conjecture turned out to be false, it was widely believed that such a colouring always contains a rainbow cycle of length almost n. In this paper, improving on several earlier results, we confirm this by proving that every properly edge-coloured Kn has a rainbow cycle of length n − O(n3/4). One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured Kn formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular, it has very good expansion properties.

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

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

U2 - 10.1007/s11856-017-1592-x

DO - 10.1007/s11856-017-1592-x

M3 - Article

AN - SCOPUS:85026735515

SN - 0021-2172

VL - 222

SP - 317

EP - 331

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 1

ER -