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

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 K n has a rainbow Hamiltonian path. Although this conjecture turned out to be false, it was widely believed that such a c...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2017-10, Vol.222 (1), p.317-331
Main Authors: Alon, Noga, Pokrovskiy, Alexey, Sudakov, Benny
Format: Article
Language:English
Subjects:
Algebra
Analysis
Applications of Mathematics
Graph coloring
Graph theory
Group Theory and Generalizations
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 K n 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 K n 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 K n 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.
ISSN:0021-2172
1565-8511
DOI:10.1007/s11856-017-1592-x