Essentially tight bounds for rainbow cycles in proper edge-colourings

Noga Alon, Matija Bucić, Lisa Sauermann, Dmitrii Zakharov, Or ZamirProceedings of the London Mathematical Society 2023 · arXiv

TL;DR

This paper provides an essentially tight answer to a long-standing question in extremal graph theory: how many edges are needed in a properly colored graph to guarantee a "rainbow cycle" (a cycle where every edge has a unique color)? The authors prove an upper bound of $O(\log n \log \log n)$ for the average degree, nearly matching the known lower bound of $\Omega(\log n)$ and significantly improving upon the previous best bound of $O(\log^2 n)$.

What Problem Does This Paper Address?

In the world of extremal graph theory, researchers ask: "How large must a structure be to guarantee a specific pattern?" A classic result is that any graph with $n$ vertices and $n$ edges must contain a cycle. However, if we add colors to the edges, the problem becomes much more complex.

A proper edge-coloring is one where no two edges sharing a vertex have the same color. A rainbow cycle is a cycle where every edge has a different color. In 2007, Keevash, Mubayi, Sudakov, and Verstraëte asked for the maximum average degree a properly colored $n$-vertex graph can have without containing a rainbow cycle.

While a standard cycle is guaranteed by an average degree of 2, a rainbow cycle is much harder to "force." Previous research had whittled the upper bound down from $O(n^{1/3})$ to $O(\log^2 n)$, but a gap remained between that and the $\Omega(\log n)$ lower bound provided by hypercube graphs. This paper essentially closes that gap.

Methods

The authors employ a sophisticated blend of probabilistic methods and structural graph theory:

  1. Robust Sublinear Expanders: The proof begins by "passing to an expander." They show that any graph contains a subgraph that is a "robust sublinear expander"—a graph that maintains strong connectivity and expansion properties even after a significant number of edges are deleted.
  2. Randomized Color Splitting: To find a rainbow cycle, the authors randomly split the available colors into two sets. If they can find two different rainbow paths between the same two vertices using disjoint color sets, the union of those paths forms a rainbow cycle.
  3. Iterative Expansion Analysis: The core of the proof involves a carefully designed random process. They analyze how the set of "rainbow-reachable" vertices grows as they reveal colors.
  4. Multiple Exposure Arguments: A key technical innovation is a "robust" expansion argument. They show that even if expansion doesn't happen at every single step of their process, it happens "often enough" (either going forward or looking backward from a step) to guarantee the set of reachable vertices eventually covers more than half the graph.

Datasets

As a theoretical mathematics paper, no empirical datasets were used. The results are proven through mathematical induction, probabilistic analysis, and combinatorial arguments.

Key Insights and Ideas

  • The Power of Robustness: Previous approaches using expanders were limited by how much "damage" the expansion could take. By using a more robust definition of expansion (Definition 3.1), the authors could handle the "loss" of colors during the search for a rainbow path more effectively.
  • Forward vs. Backward Expansion: A major "aha moment" in the proof is the realization that they don't need expansion at every step. They prove that if a set doesn't expand significantly in one step, it must have expanded significantly in the previous one. This "averaging" of expansion allows them to push the bound lower than previous methods.
  • The Additive Number Theory Bridge: The authors highlight a deep connection between rainbow cycles and dissociated sets in group theory (sets where no non-trivial product of elements equals the identity). This allows them to translate their graph theory result into a new bound for the "additive dimension" of non-abelian groups.

Key Results

  • Theorem 1.1: Every properly edge-colored graph on $n$ vertices with average degree at least $C \log n \log \log n$ contains a rainbow cycle. This is the first bound of the form $(\log n)^{1+o(1)}$.
  • Proposition 1.2: They provide tight bounds for $r$-almost rainbow cycles (where each color can appear at most $r$ times), showing a smooth transition between the rainbow and non-rainbow cases.
  • Theorem 1.5: They extend Sanders’ Theorem from additive number theory to non-abelian groups, proving that for any finite subset $A$ of a group with small doubling ($|A \cdot A| \leq K|A|$), the additive dimension is at most $O(K \log |A| \log \log |A|)$.

Limitations and Future Work

The authors acknowledge that a small gap still remains:

  • The $\log \log n$ Factor: Their upper bound is $O(\log n \log \log n)$, while the lower bound is $\Omega(\log n)$. They pose Question 10.1: Is that extra $\log \log n$ factor actually necessary? They provide some "circumstantial evidence" (based on Hamming graphs) suggesting it might be, but the question remains open.
  • Decomposition Conjectures: They propose a new question (Question 10.2) about whether properly colored expanders can be decomposed into two spanning connected subgraphs with disjoint colors, which would provide an alternative path to the tightest possible bound.

Summary updated

Abstract

An edge-coloured graph is said to be rainbow if no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on $n$ vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of $(\log n)^{2+o(1)}$ for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the $o(1)$ term in Tomon's bound, showing a bound of $O(\log^2 n)$. We prove an upper bound of $(\log n)^{1+o(1)}$ for this maximum possible average degree when there is no rainbow cycle. Our result is tight up to the $o(1)$ term, and so it essentially resolves this question. In addition, we observe a connection between this problem and several questions in additive number theory, allowing us to extend existing results on these questions for abelian groups to the case of non-abelian groups.
BibTeX
@inproceedings{alon2023essentially,
  author = {Noga Alon and Matija Bucić and Lisa Sauermann and Dmitrii Zakharov and Or Zamir},
  title = {{Essentially tight bounds for rainbow cycles in proper edge-colourings}},
  booktitle = {Proceedings of the London Mathematical Society},
  year = {2023},
}
Figure