paper

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

arXiv:2610.42094

Abstract

For an integer and , we construct a bipartite graph whose two vertex classes are disjoint copies of the family of all -subsets of a -element set, two vertices being adjacent when their sets intersect in at most elements. Assigning each vertex its corresponding subset as its color list, is not colorable, and thus its choice number . This implies that there are graphs with maximum degree and When , consequently 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).

arXiv comment17 pages