Sparse hypergraphs and pebble game algorithms

DOI10.1016/J.EJC.2008.12.018zbMATH Open1211.05097DBLPjournals/ejc/StreinuT09arXivmath/0703921OpenAlexW2061803500WikidataQ29308552 ScholiaQ29308552MaRDI QIDQ1041613

Author name not available (Why is that?)

Publication date: 3 December 2009

Published in: (Search for Journal in Brave)

Abstract: A hypergraph $G=(V,E)$ is $(k,ell)$-sparse if no subset $V^{\prime }subsetV$ spans more than $k|V^{\prime }|-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.

Full work available at URL: https://arxiv.org/abs/math/0703921

Mathematics Subject Classification ID

No records found.

This page was built for publication: Sparse hypergraphs and pebble game algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1041613)