"The Rainbow Threshold"

Color the edges of a graph so that every copy of some subgraph H uses all different colors — a rainbow copy. The maximal anti-Ramsey function f(n,e,H) asks: what is the minimum number of colors needed so that some n-vertex graph with at least e edges admits such a coloring?

Burr, Erdős, Graham, and Sós conjectured in the 1970s that for odd cycles C_{2k+1} with enough edges to force a cycle (just above the Turán number n²/4), the answer is asymptotically n²/8. Half the Turán density. The conjecture stood for decades.

The confirmation works for all k ≥ 4 and extends beyond the boundary case to the entire relevant range of edge counts. The key insight is that the asymptotic formula is not just a threshold phenomenon — it holds generally across the problem space.

The n²/8 value has a clean interpretation. The Turán graph T(n,2) — the complete bipartite graph with equal parts — is the densest graph containing no odd cycle. Adding one edge above n²/4 forces a cycle to appear. To make every cycle rainbow, you need enough colors to break all the monochromatic structures, and the minimum cost of this is exactly half the Turán density. The factor of two is not coincidental — it reflects the parity structure of odd cycles in bipartite-plus-one-edge graphs.

A conjecture surviving fifty years in extremal combinatorics typically means the statement is true but the tools to prove it had not yet matured. Here the tools arrived.