arXiv:2606.18048 · v5

List coloring uncrowded hypergraphs at the shattering threshold

在破碎阈值处对非拥挤超图进行列表染色

首次提交 2026-06-16 23:24

版本更新 2026-11-11 01:38

雷达观测 2026-11-11 13:07

摘要

A foundational theorem of Ajtai, Komlós, Pintz, Spencer, and Szemerédi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph (i.e., with girth at least $5$) of maximum degree at most $Δ$ contains an independent set of size $cn(\logΔ/Δ)^{\frac{1}{k-1}}$ for some absolute constant $c>0$. Improving an earlier bound of Frieze and Mubayi, Iliopoulos showed that every such hypergraph has list chromatic number at most $(1+o(1))(k-1)(Δ/\logΔ)^{\frac{1}{k-1}}$. Determining the optimal leading constant in this bound remains a major open problem. A natural target, suggested by the coupon-collector heuristic, is $(k-1)^{\frac{1}{k-1}}$, which also corresponds to the shattering threshold for coloring sparse random hypergraphs. Our main result shows that this target is attained: for every integer $k\ge2$, every $k$-uniform uncrowded hypergraph of maximum degree at most $Δ$ satisfies: $$χ_\ell(\mathcal{H})\le(1+o(1))\Big((k-1)\fracΔ{\logΔ}\Big)^{\frac{1}{k-1}}.$$ In particular, this confirms a 2019 conjecture of Molloy for uncrowded hypergraphs. Building on this result, we prove that every $k$-uniform linear hypergraph of maximum degree at most $Δ$ has chromatic number at most $(c_k+o(1))(Δ/\logΔ)^{\frac{1}{k-1}}$, where $c_k\to1$ as $k\to\infty$, thereby proving a conjecture of Verstraëte and Wilson on the independence number of linear hypergraphs in the stronger form of colorings. Our techniques also yield a palette sparsification theorem for uncrowded hypergraphs, partially answering a question of Casselgren and Eriksson.