A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.42094
curl -X POST /api/v1/records/arxiv/2610.42094/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.42094/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'