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

arXiv:2610.42094 · math.CO · Submitted 2026-10-30 · Read on arXiv

math.CO

Submitted: 2026-10-30

Updated: 2026-10-30

Comments: 17 pages

Code: https://github.com/chaoxu/xean

License: http://creativecommons.org/licenses/by/4.0/

The gist: For an integer k at least 2 and r 2>2(2k-1) (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…

Terminology

Abstract

For an integer k at least 2 and r 2>2(2k-1) (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 (G) at least k+1. This implies that there are graphs with maximum degree Δ and (G) at least (1 32-o(1))(Δ) squared over(Δ) cubed. When k to infinity, consequently (G)/ Δ 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).

Sources

Related papers