# Sparse hypergraphs and pebble game algorithms

 Authors: Ileana Streinu and Louis Theran Journal: European Journal of Combinatorics, 3081944–1964, 2009. Full text: arXiv • DOI

A hypergraph $G=(V,E)$ is $(k,\ell )$-sparse if no subset $V' \subset V$ spans more than $k\lvert V'\rvert − \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á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.