UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

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

Alon, N; Pokrovskiy, A; Sudakov, B; (2017) Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles. Israel Journal of Mathematics , 222 pp. 317-331. 10.1007/s11856-017-1592-x. Green open access

[thumbnail of rainbowalhc1.pdf]
Preview
Text
rainbowalhc1.pdf - Accepted Version

Download (474kB) | Preview

Abstract

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(n 3/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.

Type: Article
Title: Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/s11856-017-1592-x
Publisher version: https://doi.org/10.1007/s11856-017-1592-x
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10112655
Downloads since deposit
34Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item