@ARTICLE {hypergraphs,
title = {Sparse Hypergraphs and Pebble Game Algorithms},
author = {Streinu, Ileana and Theran, Louis},
journal = {European Journal of Combinatorics},
year = {to appear},
note = {\url{http://arxiv.org/abs/math/0703921}},
abstract = {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.},
}