Palette Sparsification for General Uniform Hypergraphs

Abstract

We prove a palette sparsification theorem for general $r$-uniform hypergraphs. For all sufficiently large $n$, every $r\ge 3$, and every $α\ge 7.1$, we show that an $n$-vertex $r$-uniform hypergraph of maximum degree $Δ$ is w.h.p. colorable from independently sampled lists of size $O(\sqrt{\log n})$ drawn from an ambient palette of size $\lceil αΔ^{1/(r-1)}\rceil$. The $\sqrt{\log n}$ dependence is asymptotically tight.

Disclosure

“AI disclosure GPT-5.6 Sol was used to quickly test intuitions, to help improve the constant coefficients, and to check for typos. It also found that the lower bound was already established in prior literature. The author takes full responsibility for all statem”

PDF page 9

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T18:14:37.381363Z

Structural counts