Random independent sets in uncrowded hypergraphs
Abstract
Given any fixed integer k ≥ 2 and sufficiently large d, we show that the largest possible fractional chromatic number of a k-uniform d-degenerate uncrowded hypergraph H (i.e., with girth at least $5$) satisfies χf(H) = (1 + od(1)) ((k−1) d/(log d))1/(k−1). In fact, we prove that this holds for k-uniform d-degenerate hypergraphs of girth at least g, for any given g ≥ 5. As a corollary, we obtain improved bounds on the fractional chromatic number of d-degenerate linear hypergraphs. This work builds upon a recent result by Allen, Dhawan, and Noel, extending it from graphs to hypergraphs. In addition to overcoming the new difficulties that arise in the hypergraph setting, our approach yields a simpler proof even in the original graph case. Our proof of the upper bound uses a simpler iterative procedure for sampling independent sets. We also establish bounds for fractional colorings with local demands, a framework introduced by Kelly and Postle, verifying a recent conjecture of Yu and Zhang. As a consequence, we obtain a degree-sequence bound on the independence number of uncrowded hypergraphs with a leading constant matching the shattering threshold. For the matching lower bound, we use a hypergraph variant of the uniform attachment model and harmonic vertex weights to bound the fractional chromatic number via linear programming duality, then remove all short cycles by deleting vertices of negligible total weight. We also replace the Catalan-number argument used in the graph case with a matrix-norm estimate, simplifying the analysis.
Related
BibTeX
@misc{dhawan2026random,
title = {{Random independent sets in uncrowded hypergraphs}},
author = {Abhishek Dhawan and Lina Li and Abhishek Methuku and Minh-Quan Vo and Kewen Yuan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08707},
eprint = {2610.08707},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08707},
}
RIS
TY - UNPB
TI - Random independent sets in uncrowded hypergraphs
AU - Abhishek Dhawan
AU - Lina Li
AU - Abhishek Methuku
AU - Minh-Quan Vo
AU - Kewen Yuan
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.08707
UR - https://arxiv.org/abs/2610.08707
AB - Given any fixed integer k ≥ 2 and sufficiently large d, we show that the largest possible fractional chromatic number of a k-uniform d-degenerate uncrowded hypergraph H (i.e., with girth at least $5$) satisfies χ_f(H) = (1 + o_d(1)) ((k−1) d/(log d))^1/(k−1). In fact, we prove that this holds for k-uniform d-degenerate hypergraphs of girth at least g, for any given g ≥ 5. As a corollary, we obtain improved bounds on the fractional chromatic number of d-degenerate linear hypergraphs. This work builds upon a recent result by Allen, Dhawan, and Noel, extending it from graphs to hypergraphs. In addition to overcoming the new difficulties that arise in the hypergraph setting, our approach yields a simpler proof even in the original graph case. Our proof of the upper bound uses a simpler iterative procedure for sampling independent sets. We also establish bounds for fractional colorings with local demands, a framework introduced by Kelly and Postle, verifying a recent conjecture of Yu and Zhang. As a consequence, we obtain a degree-sequence bound on the independence number of uncrowded hypergraphs with a leading constant matching the shattering threshold. For the matching lower bound, we use a hypergraph variant of the uniform attachment model and harmonic vertex weights to bound the fractional chromatic number via linear programming duality, then remove all short cycles by deleting vertices of negligible total weight. We also replace the Catalan-number argument used in the graph case with a matrix-norm estimate, simplifying the analysis.
ER -