Sparse Hypergraphs and Pebble Game Algorithms
<|reference_start|>Sparse Hypergraphs and Pebble Game Algorithms: A hypergraph $G=(V,E)$ is $(k,\ell)$-sparse if no subset $V'\subset V$ spans more than $k|V'|-\ell$ hyperedges. We characterize $(k,\ell)$-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lov{\'{a}}sz, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behaviour in terms of the sparsity parameters $k$ and $\ell$. Our constructions extend the pebble games of Lee and Streinu from graphs to hypergraphs.<|reference_end|>
@article{streinu2007sparse,
    title={Sparse Hypergraphs and Pebble Game Algorithms},
    author={Ileana Streinu and Louis Theran},
    journal={arXiv preprint arXiv:math/0703921},
    year={2007},
    archivePrefix={arXiv},
    eprint={math/0703921},
    primaryClass={math.CO cs.DS}
}