A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs

Introduction

Graph coloring is a fundamental area of study in extremal combinatorics, and one question with a large amount of recent progress is the structure of properly edge-colored graphs. A cycle in an edge-colored graph is called rainbow if no color appears more than once, and the work of [18] raised the question of the number of edges (equivalently, the average degree) needed to guarantee the existence of a rainbow cycle. Their work showed a lower bound on the average degree of $\Omega(\log n)$, and a long line of work [9 Jan20, 22, 16, 15] culminating in [1] proved this is nearly tight, showing that properly edge-colored graphs with average degree $\Omega(\log n \log\log n)$ must contain a rainbow cycle (closing this $\log\log n$ gap remains an open question). The rainbow cycle theorem of [1] has found many applications, notably in coding theory.

A binary code $E : \mathbb{F}_2^k \to\mathbb{F}_2^n$ is called a $(r,\delta)$-locally correctable code, abbreviated as $(r,\delta)$-LCC, if any codeword $E(x)$ has at most a $\delta$ fraction of coordinates flipped to produce some $y \in\mathbb{F}_2^n$, for each coordinate $i \in[n]$, there exists an algorithm which queries at most $r$ coordinates of $y and outputs the $i$th bit $E(x)_i$ of the original codeword with nontrivial probability. LCCs were introduced for program checking [8], and played a central role in the proof of the PCP theorem [5, 4], among numerous other applications. A central question in the study of LCCs is determining the optimal rate (the ratio of the message length $k$ to the blocklength $n$ of a codeword) of a $r$-query LCC.

Until recently, lower bounds on LCCs were simply those of locally decodable codes, or LDCs, where instead of the code admitting $r$-query decoding algorithms which can output the $i$th bit of the codeword $E(x)$, we only need to have $r$-query decoding algorithms for each bit $x_i$, $i \in[k]$ of the message. 1-LDCs do not exist [19] and for 2-LDCs, we have an exponential lower bound of $k \le\widetilde{O}(\log n)$ on the blocklength, which is tight [20, 10]. These results carry over to LCCs. For even $r \ge4$-LDCs, the best lower bounds are $k \le\widetilde{O}(n^{1-2/r})$ [23, 24, 25, 6], and for odd $r$-LDCs, the best known bounds were simply those of even $(r+1)$-LDCs (since any $r$-LDC is also a $(r+1)$-LDC) until a breakthrough work of [3] proved $k \le\widetilde{O}(n^{1-2/r})$ for $r=3$ using the Kikuchi Method, at the same time also giving a simple proof of the even $r$ case. The follow-up works of [7, 14] generalized the Kikuchi method to obtain the same bound for all odd $r \ge5$. For linear 3-LCCs, [17] obtained an exponential $k \le O(\log^8 n)$ lower bound, which was later improved to $k \le O(\log^4 n)$ by [26] (see also [21]), which, prior to the rainbow cycle theorem, were the only results showing a stronger lower bound for linear $r$-LCCs over a constant-sized $\mathbb{F}_q$ compared for those known for $r$-LDCs.

The work of [2] showed a surprising connection between LCCs and rainbow cycles, proving a reduction from binary linear $r$-LCC lower bounds to a stronger notion of "rainbow" $(r-1)$-LDC lower bounds. By using the rainbow cycle theorem of [1], they prove rainbow lower bounds for even $r$-LDCs, implying a near-optimal bound of $k \le O(\log^2 n\log\log n)$ for binary linear 3-LCCs, nearly matching the $k=O(\log^2 n)$ given by Reed-Muller codes. They also obtain an improved $k \le\widetilde{O}(n^{1-2/(r-1)})$ lower bound for odd $r$-LCCs. However, this does not work for even $r$-LCCs, as we cannot reduce odd LDC lower bounds to analyzing edge-colored graphs where each edge is assigned exactly one color; instead, the graphs here have edges colored by a pair of colors. This in turn motivates the question of proving a generalization of the rainbow cycle to list-colored graphs.

Our results

Our main result is the following theorem, which generalizes the result of [1] to weighted, locally bounded list-colored graphs.

Using this theorem, we close the gap between even and odd $r$-LCCs, proving the following lower bound for all $r$.

Technical Overview

In this section, we give an overview of the proofs of Theorems 1.1 and 1.2. We first summarize the Kikuchi method of [3 HKM+25, 2, 7, 14] for LDC/LCC lower bounds and the approach of [1] for the rainbow cycle theorem.

Kikuchi graphs and LDCs/LCCs. Given a linear $r$-LDC, standard reductions allow us to prove lower bounds for normal linear LDCs, which have the property that for each bit $i \in[k]$ of the message, there exists a $r$-uniform size-$\Omega(n)$ hypergraph matching $\mathcal{H}_i$ on $[n]$ such that to decode the $i$th bit $x_i$ of a message $x$ given the encoding $E(x)$, we simply pick any $C \in\mathcal{H}_i$, and take the XOR of the coordinates in $C$ of $E(x)$. We note that if we have an even cover (a set of hyperedges $C_1,\cdots,C_t$ such that $\bigoplus_{u \in[t]} C_u = \varnothing$, i.e. it cover every vertex an even (possibly 0) number of times), such that there is some $\mathcal{H}_i$ such that we use an odd number of hyperedges from $\mathcal{H}_i$, then taking the XOR of all $E(x)_i$, $i \in C_u$, will return 0. However, letting $C_u \in\mathcal{H}_{i_u}$ for all $u$, the normal LDC decoding property implies that this is equal to the XOR of the $i_u$th bit of $x$, and since there is some $x_i$ that appears an odd number of times, this is not equal to 0 if $x_i = 1$. Therefore, proving a bound of $k < k(r,n)$ for all $r$-LDCs is equivalent to showing that when $k \geq k(r,n)$, any set of $\Omega(n)$, $r$-uniform hypergraph matchings contains an even cover using some $\mathcal{H}_i$ an odd number of times.

For even $r$, [3] constructs a level-$\ell$ Kikuchi graph, which has vertex set consisting of all size-$\ell$ subsets of $[n]$, and edges between any two $S,T \in\binom{[n]}{\ell}$ such that the symmetric difference $S \oplus T$ is a hyperedge. Any cycle in the Kikuchi graph corresponds to an even cover in the set of hypergraph matchings, and by coloring an edge $(S,T)$ with color $i$ if $S \oplus T \in\mathcal{H}_i$, a sufficient condition for the desired even cover property is to find a cycle which uses some color exactly once, which we call an weak rainbow cycle. By deleting a $\frac{1}{2}$ fraction of edges, we can make the Kikuchi graph properly edge colored, after which classic results [18] show the existence of a weak rainbow cycle.

For odd $r$-LDCs, the aforementioned definition of Kikuchi graphs does not work: the symmetric difference of any two size-$\ell$ sets is always even and thus can never be a hyperedge in one of the odd $r$-uniform hypergraph matchings we have. Instead, [3 HKM+25, 7, 14] consider pairs of hyperedges $C \in\mathcal{H}_i,C' \in\mathcal{H}_j$ from separate matchings with nonempty intersection, instead connecting two Kikuchi vertices $S,T$ if $S \oplus T = C \oplus C'$ and coloring the edge with a pair of colors $\{i,j\}$¹. As before, finding a weak rainbow cycle is sufficient for proving the desired even cover property, and this can be done using results for list-colored graphs from [18]. Thus, for LDCs, we have matching lower bounds for odd $r$-LDCs.

[2] show that if for all $k \geq k'(r-1,n)$, any set of size-$\Omega(n)$, $(r-1)$-uniform hypergraph matchings $\mathcal{H}_1 \cup\cdots\cup\mathcal{H}_k$ contains a rainbow even cover, meaning an even cover using at most one hyperedge from each $\mathcal{H}_i$, then for every binary linear $r$-LCC, we have $k \lesssim k'(r-1,n)\log n$. When $r-1$ is even, they apply the result of [1] to the Kikuchi graph for even LDCs to show the existence of a rainbow cycle and therefore a rainbow even cover. However, the rainbow cycle theorem does not apply to list-colored graphs, so they do not obtain the same result when $r-1$ is odd.

Finding rainbow cycles: current approaches and barriers to generalization. [1] makes use of robust sublinear expanders, which are graphs in which any subset $S$ of $n^{1-\varepsilon}$ vertices has a size $\Omega(\varepsilon|S|)=\Omega\left(|S|\left(1-\frac{\log|S|}{\log n}\right)\right)$ neighborhood even after $\Omega(\varepsilon d_{\mathrm{avg}}|S|)$ edges incident to $S$ are adversarially deleted. Given a properly edge-colored graph $G$ with color set $\mathcal{C}$, they find a robust sublinear expander subgraph $H$ and obtain a rainbow cycle $H$ as follows: first, pick an arbitrary vertex $x \in V(H)$, and partition $\mathcal{C}=\mathcal{C}'\sqcup\mathcal{C}''$ uniformly at random. Then if there is a vertex $y \in V(H)$ reachable from $x$ by both a rainbow path using only colors in $\mathcal{C}'$, and a rainbow path using only colors in $\mathcal{C}''$, then the union of the two paths is a rainbow cycle in $H$. By showing that the set $U(\mathcal{C}')$ of all vertices reachable from $x$ via a rainbow path in $\mathcal{C}'$ has size $>\frac{n+1}{2}$ with probability $>\frac{1}{2}$, one can show that $U(\mathcal{C}')$ and $U(\mathcal{C}'')$ (defined analogously, and which has the same distribution as $U(\mathcal{C}')$) intersect with positive probability and therefore one can find a rainbow cycle.