arXiv preprint ·
A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Combinatorics
Testing Implies Distance Estimation with Polynomial Loss
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models
How Unbalanced Must a Latin Rectangle Be?
A Polynomial Erdős-Pósa bound for Eulerian digraphs
Get the few papers worth your time in Combinatorics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.