Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 29 min ago
PreprintarXiv licencearXiv

Streaming Hypergraph Coloring via Palette Sparsification

  • Artur Czumaj
  • Pan Peng
  • Ruizhe Shi
  • Christian Sohler
Open at sourcePDFDOICite

Abstract

For every fixed k≥2, 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 Õ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 Θ(√(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 bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of Δ for which any deterministic one-pass algorithm requires exp(ΔΩ(1)) colors.

Related

  1. Exact-palette rainbow embeddings in uniformly coloured pseudorandom graphs
    Elad Aigner-Horev, Dan Hefetz, Yury Person +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Layerwise Decoupling for Stable Structured Sparsification of Fully Connected Layers
    Charles Kulick, Armenak Petrosyan, Sui Tang
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Convex Regression at Scale: Geometry-Preserving Constraint Sparsification
    Anish Senapati, Jose Blanchet
    arXivPreprintCC BY 4.0Full textOptimisation & controlStatisticsarXiv
  4. Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems
    Fulin Yan, François Clautiaux, Aurélien Froger
    HALPreprintCC BY-NC 4.0Full textGeneral mathematicsHAL
  5. Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
    Yuichi Yoshida
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{czumaj2026streaming,
  title = {{Streaming Hypergraph Coloring via Palette Sparsification}},
  author = {Artur Czumaj and Pan Peng and Ruizhe Shi and Christian Sohler},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.19623},
  eprint = {2608.19623},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.19623},
}
RIS
TY  - UNPB
TI  - Streaming Hypergraph Coloring via Palette Sparsification
AU  - Artur Czumaj
AU  - Pan Peng
AU  - Ruizhe Shi
AU  - Christian Sohler
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2608.19623
UR  - https://arxiv.org/abs/2608.19623
AB  - For every fixed k≥2, 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 Õ_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 Θ(√(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 bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of Δ for which any deterministic one-pass algorithm requires exp(Δ^Ω(1)) colors.
ER  -