A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
Abstract
For an integer k≥ 2 and r2>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)≥ k+1. This implies that there are graphs with maximum degree Δ and ch(G)≥(1/32−o(1))(lnΔ)2/(lnlnΔ)3. When k→∞, consequently ch(G)/lnΔ 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).
Related
- A counterexample to the Erdős--Sós bipartite-link conjecture
- A counterexample to a mixing-time conjecture for repeated averages on graphs
- Proper conflict-free choosability of sparse graphs with girth at least seven
- Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
- Proper Conflict-Free Choosability for Graphs with Bounded Average Degree
BibTeX
@misc{yu2026counterexample,
title = {{A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs}},
author = {Junran Yu and Gexin Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42094},
eprint = {2610.42094},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42094},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
AU - Junran Yu
AU - Gexin Yu
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42094
UR - https://arxiv.org/abs/2610.42094
AB - For an integer k≥ 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)≥ k+1. This implies that there are graphs with maximum degree Δ and ch(G)≥(1/32−o(1))(lnΔ)^2/(lnlnΔ)^3. When k→∞, consequently ch(G)/lnΔ 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).
ER -