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.