{"id":"arxiv/2608.19623","url":"https://arxiv.org/abs/2608.19623","tags":["math.CO","cs.DM","cs.DS"],"score":0,"title":"Streaming Hypergraph Coloring via Palette Sparsification","domain":"math.CO","source":"arxiv","authors":["Artur Czumaj","Pan Peng","Ruizhe Shi","Christian Sohler"],"reviews":0,"subject":"math.CO","summary":"For every fixed $k\\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $Δ$ with $O(Δ^{1/(k-1)})$ colors using $\\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palette-sparsification theorem for general uniform hypergraphs. Independently sampled lists of $Θ(\\sqrt{\\log n})$ colors from a palette of size $O(Δ^{1/(k-1)})$ preserve colorability with high probability; the list-size dependence is asymptotically optimal. These results extend to…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-20","reactions":{}}