A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs

Abstract

For an integer $k\ge 2$ and $r^2>2(2k-1)\ln (2k-1)$, we construct a bipartite graph $G$ whose two vertex classes are disjoint copies of the family of all $k$-subsets of a $(2k-1)$-element set, two vertices being adjacent when their sets intersect in at most $r$ elements. Assigning each vertex its corresponding subset as its color list, $G$ is not colorable, and thus its choice number $\ch(G)\ge k+1$. This implies that there are graphs with maximum degree $\Delta$ and $$\ch(G)\ge\Bigl(\frac1{32}-o(1)\Bigr)\frac{(\ln\Delta)^2}{(\ln\ln\Delta)^3}.$$ When $k\to\infty$, consequently $\ch(G)/\ln\Delta$ tends to infinity, which disproves the Alon--Krivelevich conjecture. In order to show the uncolorability, we use tools from probability (conditional product measure, nested coupling, and Doob martingale), which we write in an elementary language of weighted counting, and topology (Brouwer fixed-point theorem).