### 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 317-331 |

Number of pages | 15 |

Journal | Israel Journal of Mathematics |

Volume | 222 |

Issue number | 1 |

DOIs | |

State | Published - Oct 1 2017 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles'. Together they form a unique fingerprint.

## Cite this

*Israel Journal of Mathematics*,

*222*(1), 317-331. https://doi.org/10.1007/s11856-017-1592-x