Affordable Access

Publisher Website

Sparse hypergraphs and pebble game algorithms

Authors
Journal
European Journal of Combinatorics
0195-6698
Publisher
Elsevier
Publication Date
Volume
30
Issue
8
Identifiers
DOI: 10.1016/j.ejc.2008.12.018
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract A hypergraph G = ( V , E ) is ( k , ℓ ) -sparse if no subset V ′ ⊂ V spans more than k | V ′ | − ℓ hyperedges. We characterize ( k , ℓ ) -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 behavior in terms of the sparsity parameters k and ℓ . Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.

There are no comments yet on this publication. Be the first to share your thoughts.