Paperlane

no. 13 · Wednesday 11 November 2026

The Proof of the Alon–Kim Conjecture

Chengshuo Qiao, Zhijun Lu and Huimin Song

math.CO · 25 pp

Abstract

In 1997, Alon and Kim proposed an asymptotic edge-coloring bound motivated by a bound on the number of edges in intersecting uniform hypergraphs. The Alon–Kim conjecture asserts that, for fixed integers $k\ge t\ge1$ and $\varepsilon>0$, every $k$-uniform multihypergraph $H$ in which any two distinct edges intersect in at most $t$ vertices satisfies $χ'(H)\le(t-1+\frac{1}{t}+\varepsilon)Δ(H)$ whenever $Δ(H)$ is sufficiently large. In this paper, we prove the Alon–Kim conjecture. Our method combines finite-dimensional convex optimization with probabilistic methods.

comments
25 pages
fields
Combinatorics
pdf ↗ page arXiv:2611.13698 ↗