Sparse Hypergraphs and Pebble Game Algorithms
| dc.creator | Streinu, Ileana | |
| dc.creator | Theran, Louis | |
| dc.date | 2007-03-30 | |
| dc.date.accessioned | 2026-07-07T08:08:53Z | |
| dc.date.available | 2026-07-07T08:08:53Z | |
| dc.description | 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{á}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. | |
| dc.identifier | https://arxiv.org/abs/math/0703921 | |
| dc.identifier | http://arxiv.org/abs/math/0703921 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/131413 | |
| dc.subject | Combinatorics | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | 05C65; 05C85; 68R10; 05B35 | |
| dc.title | Sparse Hypergraphs and Pebble Game Algorithms | |
| dc.type | text |