{"id":"arxiv/2610.42094","url":"https://arxiv.org/abs/2610.42094","tags":["math.CO"],"score":0,"title":"A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs","domain":"math.CO","source":"arxiv","authors":["Junran Yu","Gexin Yu"],"reviews":0,"subject":"math.CO","summary":"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 $Δ$ and $$\\ch(G)\\ge\\Bigl(\\frac1{32}-o(1)\\Bigr)\\frac{(\\lnΔ)^2}{(\\ln\\lnΔ)^3}.$$ When $k\\to\\infty$, consequently $\\ch(G)/\\lnΔ$ tends to…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}