The Alon-Krivelevich conjecture asserts that there is an absolute constant 
such that every finite simple
graph that is bipartite of maximum
vertex degree 
has choice number
at most 
(Alon and Krivelevich 1998).
Yu and Yu (2026) disprove the conjecture by constructing bipartite graphs with
 |
as 
along their family. For integers 
and 
, the two parts are disjoint copies of all 
-element subsets of a 
-element set. Two vertices
are adjacent when their corresponding subsets intersect
in at most 
elements. With each list coloring list equal to
its corresponding subset, no proper
list coloring exists whenever 
. Yu and Yu (2026) credit an OpenAI model
with finding the construction and proof and report independently
checking the mathematical content.
