Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 18 min ago
PreprintCC BY 4.0arXiv

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

  • Andrew D. Lin
Open at sourcePDFDOICite

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 nloglog n) always contains a rainbow cycle, and generalize it to weighted graphs with edges list colored with list size at most ℓ and where the total weight of all edges containing a given color i incident to a vertex is at most Δ, showing that Ωℓ(Δlog nloglog n) average degree guarantees a rainbow cycle. Using the reduction of [AG26] and the new generalized rainbow cycle theorem, we prove that for r≥ 3, every binary linear r-query locally correctable code E:𝔽2k→ 𝔽2n satisfies k≤ Õ(n1−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.

Related

  1. Improved bounds in Birch's theorem for forms in many variables
    Yijie Diao, Lena Wurzinger
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. Improved Bounds for the Entropic Central Limit Theorem in the Log-Concave Case
    Tom Maitre
    HALPreprintCC BY 4.0Full textProbabilityHALarXiv
  3. Three Improved Lower Bounds for Binary Error-Correcting Codes
    Kazuki Ota, Takayuki Osa, Tatsuya Harada
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  4. Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
    Hassan Khodaiemehr, Chen Feng, Tolga M. Duman
    arXivPreprintCC BY-NC-ND 4.0Full textGeneral mathematicsarXiv
  5. A Bondy-type theorem for rainbow pancyclicity in graph systems
    Ailian Chen, Liping Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lin2026short,
  title = {{A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs}},
  author = {Andrew D. Lin},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05034},
  eprint = {2611.05034},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05034},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
AU  - Andrew D. Lin
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05034
UR  - https://arxiv.org/abs/2611.05034
AB  - 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 nloglog n) always contains a rainbow cycle, and generalize it to weighted graphs with edges list colored with list size at most ℓ and where the total weight of all edges containing a given color i incident to a vertex is at most Δ, showing that Ω_ℓ(Δlog nloglog n) average degree guarantees a rainbow cycle. Using the reduction of [AG26] and the new generalized rainbow cycle theorem, we prove that for r≥ 3, every binary linear r-query locally correctable code E:𝔽_2^k→ 𝔽_2^n satisfies k≤ Õ(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.
ER  -