Sparse hypergraphs and pebble game algorithms

DOI10.1016/J.EJC.2008.12.018MaRDI QIDQ1041613zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ileana Streinu, Louis Theran

Publication date 3 December 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703921, https://scholarworks.smith.edu/cgi/viewcontent.cgi?article=1014&context=csc_facpubs

Mathematics Subject Classification ID

Hypergraphs (05C65) Games involving graphs (91A43)

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.

Recommendations

• Pebble game algorithms and sparse graphs
• Pebble game algorithms and \((k,l)\)-sparse graphs
• On sparse discretization for graphical games
• scientific article; zbMATH DE number 4189511
• Pebbling and optimal pebbling in graphs
• Inapproximability of the standard pebble game and hard to pebble graphs
• Pebble games and cospectral graphs
• Decomposition of sparse graphs, with application to game coloring number
• Optimal pebbling of graphs
• Graph pebbling: a blend of graph theory, number theory, and optimization

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3512137 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 2188414 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A generalization of Kónig's theorem
• A matroid approach to finding edge connectivity and packing arborescences
• A network theory approach to the rigidity of skeletal structures. I: Modelling and interconnection
• A network theory approach to the rigidity of skeletal structures. II: Laman's theorem and topological formulae
• Algorithms for graph rigidity and scene analysis
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Edge-Disjoint Spanning Trees of Finite Graphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Minimum partition of a matroid into independent subsets
• On Generic Rigidity in the Plane
• On constructive characterizations of (k,l)-sparse graphs
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• On graphs and rigidity of plane skeletal structures
• On the Problem of Decomposing a Graph into n Connected Factors
• Pebble game algorithms and sparse graphs
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Submodular functions and independence structures
• The Union of Matroids and the Rigidity of Frameworks

Cited in

(20)

• Inapproximability of the standard pebble game and hard to pebble graphs
• Natural realizations of sparsity matroids
• Combinatorial rigidity and independence of generalized pinned subspace-incidence constraint systems
• Sparse graphs are near-bipartite
• New upper bounds for the number of embeddings of minimally rigid graphs
• Combinatorial rigidity of incidence systems and application to dictionary learning
• Sparse graphs and an augmentation problem
• scientific article; zbMATH DE number 4189511 (Why is no real title available?)
• Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials
• A note on \([k,l]\)-sparse graphs
• Body-and-cad geometric constraint systems
• On the target pebbling conjecture
• Sparsity-certifying graph decompositions
• Pebble game algorithms and sparse graphs
• Spy game: FPT-algorithm, hardness and graph products
• Volume rigidity and algebraic shifting
• Multitriangulations as complexes of star polygons
• Pebble game algorithms and \((k,l)\)-sparse graphs
• Sparse hypergraphs with applications in combinatorial rigidity
• Globally rigid augmentation of rigid graphs

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)