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.
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 |
Archive Staff Only
View Item |