Sparse Hypergraphs and Pebble Game Algorithms

Details Sparse Hypergraphs and Pebble Game Algorithms Sparse Hypergraphs and Pebble Game Algorithms

2007-03-30

arxiv.org/abs/math/0703921v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sparse Hypergraphs and Pebble Game Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparse Hypergraphs and Pebble Game Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse Hypergraphs and Pebble Game Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-651021