Rainbow cycle theorem strengthened and coding limits improved for error correction
A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
Computational ComplexityInformation Theory
Summary
This paper deals with special patterns called rainbow cycles in networks where edges have colors or weights. The authors provide a simpler way to prove that certain colorful networks must contain these rainbow cycles, even under more general conditions. They then apply these findings to improve the understanding of locally correctable error-correcting codes, which help fix errors in digital data efficiently. Their work closes a known gap in mathematical bounds for a particular type of error-correcting codes, telling us more precisely how good these codes can be.
What this means in practice
- •For coding engineers: Design error-correcting codes with improved understanding of limitations on code size versus error query capabilities.
- •For network algorithm developers: Validate the presence of diverse edge patterns in large complex networks under weighted and list-colored constraints.
A theory result. No direct application yet.
Authors
Andrew D. Lin
Abstract
A \emph{rainbow cycle} in a list-edge-colored graph is a cycle where no color appears more than once. We give a short and simple proof of a result of [ABSZZ] showing that a properly edge-colored $n$-vertex graph with average degree $Ω(\log n\log\log n)$ always contains a rainbow cycle, and generalize it to weighted graphs with edges list colored with list size at most $\ell$ and where the total weight of all edges containing a given color $i$ incident to a vertex is at most $Δ$, showing that $Ω_\ell(Δ\log n\log\log n)$ average degree guarantees a rainbow cycle. Using the reduction of [AG26] and the new generalized rainbow cycle theorem, we prove that for $r\geq 3$, every binary linear $r$-query locally correctable code $E:\mathbb{F}_2^k\rightarrow \mathbb{F}_2^n$ satisfies $k\leq \tilde{O}(n^{1-2/(r-1)})$ by showing a rainbow analogue of the odd $r$-LDC lower bounds of [BHKL25,JM25], closing the gap between the best known lower bounds for odd- and even-query binary linear $r$-LCCs.