Sharp Choice Number Thresholds for Complete Bipartite Graphs

Fix m≥3. The choice number ch(Km,n) of the complete bipartite graph Km,n has two sharp thresholds as n grows. We give complete proofs of the Hoffman–Johnson values at levels m+1 and m, and we pin down the extremal list assignments at the lower threshold n0=(m−1)m−1−(m−2)m−1. Specifically, ch(Km,n)=m+1,n≥mm,m,n0≤n<mm,≤m−1,n<n0. Our method centers on a transversal obstruction principle and a dichotomy for how the M-side lists can intersect when all lists have size m−1: Case I, in which some m−1 of the M-lists are pairwise disjoint, and Case II, in which three M-lists pairwise intersect with all remaining lists mutually disjoint. For m≥5 we show that the three-way intersection pattern (three pairwise intersecting M-lists) is strictly non-extremal, and we prove the uniqueness of extremal configurations: we classify all uniformly critical assignments at n0 and show that, up to relabeling, there are exactly two extremal types for m≥5, while a third type appears for m∈{3,4}. Finally, we propose a fixed-k block model for deeper levels ch(Km,n)=m−k+1 and contrast this unbalanced setting with the balanced case m=n, where ch(Km,m)∼log2m, highlighting the shift from polynomial to logarithmic threshold growth.