Abstract
This paper addresses the long-standing problem of finding long rainbow cycles in properly edge-coloured complete graphs. We prove that every such graph $K_n$ contains a rainbow cycle of length $n - O(n^{3/4})$. The proof utilizes a novel probabilistic lemma showing that subgraphs formed by random color classes exhibit expansion properties similar to Erdős-Rényi random graphs, combined with an iterative path-extension technique.
Introduction
In graph theory, a "properly edge-coloured" graph is one where no two edges incident to the same vertex share a color. A "rainbow" subgraph is defined as one where every edge has a distinct color. In 1980, mathematician Geňa Hahn conjectured that every properly edge-coloured complete graph ($K_n$) contains a rainbow Hamiltonian path. Although counterexamples were later found for specific values of $n$, the intuition remained that such graphs should contain rainbow cycles covering "almost all" vertices.
Prior to this work, the best-known bounds for rainbow paths were approximately $3n/4$. This paper provides a significant breakthrough by establishing a bound of $n - o(n)$, specifically finding cycles of length $n - O(n^{3/4})$.
Methodology
The authors' approach integrates the Probabilistic Method with structural graph theory through two primary components:
1. Random Color Selection
The core "engine" of the proof is a new lemma (Theorem 1.3) establishing that a subgraph formed by randomly selecting color classes from a properly edge-coloured graph inherits the edge distribution and expansion properties of a truly random (Erdős-Rényi) graph. Despite the inherent correlations between edges of the same color, the "properly coloured" constraint ensures sufficient structure for the probabilistic method to succeed.
2. Path Rotation and Expansion
Using the expansion properties of the random color subgraph, the authors employ a technique inspired by Andersen (1989). They begin by constructing a "forest" of many short rainbow paths. They then use the expansion properties to "rotate" and merge these paths, extending them until they cover nearly the entire graph.
Key Results
The primary contribution of this research is the following theorem:
- Main Theorem: For a sufficiently large $n$, every properly edge-coloured $K_n$ contains a rainbow cycle of length at least $n - 24n^{3/4}$.
Additionally, the authors established a general Expansion Lemma, proving that subgraphs formed by choosing colors with probability $p$ will, with high probability, have vertices with degree approximately $np$ and maintain a minimum number of edges between any two large vertex sets. These results were also extended to balanced complete bipartite graphs ($K_{n,n}$), with implications for the study of Latin Squares.
Discussion and Future Work
While $n - O(n^{3/4})$ represents a major advancement, the authors suggest that the error term could be further optimized. Empirical evidence suggests the true error term might be a small constant rather than a function of $n$. Furthermore, the constant "24" in the main theorem was not minimized and could likely be improved. Future research may also explore the absolute minimum set size for which the "random-like behavior" lemma holds, currently requiring sets of size approximately $(\log n)^2$.
Summary updated