{"id":"arxiv/2611.05034","url":"https://arxiv.org/abs/2611.05034","tags":["math.CO","cs.CC","cs.IT"],"score":0,"title":"A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs","domain":"math.CO","source":"arxiv","authors":["Andrew D. Lin"],"reviews":0,"subject":"math.CO","summary":"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]…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}