Metraipolis › archive › dc_325ecce2dfb9
A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs — arXiv:2610.42094
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.42094
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:18:45.990Z
- SHA-256 of the archived text
6d16cffde0f27d36c889b6db51ae790b5dd1e95b37c1ccecced03ef4307eaada- Stable URL of this page
https://metraipolis.com/documento/dc_325ecce2dfb9
How to cite
A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs — arXiv:2610.42094 — arXiv (en), https://arxiv.org/abs/2610.42094 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_325ecce2dfb9 (Metraipolis archive dc_325ecce2dfb9, sha256 6d16cffde0f27d36c889b6db51ae790b5dd1e95b37c1ccecced03ef4307eaada)
BibTeX
@misc{dc325ecce2dfb9,
title = {A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs — arXiv:2610.42094},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.42094},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_325ecce2dfb9; sha256 6d16cffde0f27d36c889b6db51ae790b5dd1e95b37c1ccecced03ef4307eaada},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42094. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Delta$ and $$\ch(G)\ge\Bigl(\frac1{32}-o(1)\Bigr)\frac{(\ln\Delta)^2}{(\ln\ln\Delta)^3}.$$ When $k\to\infty$, consequently $\ch(G)/\ln\Delta$ 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).
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.42094 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T08:05:23.795Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).