List coloring uncrowded hypergraphs at the shattering threshold
Improving an earlier bound of Frieze and Mubayi, Iliopoulos showed that any $k$-uniform uncrowded hypergraph of maximum degree $Δ$ has list chromatic number at most $(1+o(1))(k-1)\Big(\fracΔ{\logΔ}\Big)^{\frac{1}{k-1}}$. Determining the optimal leading constant in this bound remains a major open problem. A natural target for the constant, suggested by the coupon-collector heuristic, is $(k-1)^{\frac{1}{k-1}}$, which also arises independently as the shattering threshold for coloring and finding large independent sets in sparse random hypergraphs. We show that uncrowded hypergraphs attain this…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.18048
curl -X POST /api/v1/records/arxiv/2606.18048/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.18048/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'