The Proof of the Alon--Kim Conjecture

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\ge 1$ and $\epsilon >0$, every $k$-uniform multihypergraph $H$ in which any two distinct edges intersect in at most $t$ vertices satisfies ${\chi }^{\prime }(H)\le (t-1+\frac{1}{t}+\epsilon )\Delta (H)$ whenever $\Delta (H)$ is sufficiently large. In this paper, we prove the Alon--Kim conjecture. Our method combines finite-dimensional convex optimization with probabilistic methods.

arXiv comment25 pages