The hereditary counts found in the rigidity theorems for bar-joint and body-bar rigidity generalize to a larger family of (k, l)-sparse graphs.
A graph is (k, l)-sparse if any subset of n' vertices spans at most kn'-l vertices. If, in addition, it has n vertices and kn-l edges, it is (k, l)-tight.
In the language of abstract sparsity, the minimally rigid 2D bar-and-joint frameworks are (2,3)-tight. The minimally rigid 3D body-bar frameworks are (6,6)-tight.
We generalize the pebble games for rigidity to all (k, l)-sparse graphs for k and l such that l∈[0, 2k). The initial configuration and basic moves are given as follows.
Here we see the components pebble game for (3,3)-sparse graphs. (The components of a sparse graph are its maximal tight subgraphs.)
Generalizing the results from pebble game for rigidity, we have an equivalence between (k, l)-sparse graphs and graphs that can be constructed with the (k, l)-pebble game.
The graphs that can be constructed using the (k, l)-pebble game are exactly (k, l)-sparse graphs. The order in which the edges are considered does not matter.
A graph-theoretic application of (k, l)-pebble games relates to graphs that decompose into edge-disjoint spanning trees, which are called arborescences. A fundamental result of graph theory is that (k,k)-sparsity and arboricity are equivalent concepts. (One direction is easy to see, since each tree contributes at most n'-1 edges to any subgraph.)
A graph admits a decomposition into k edge-disjoint spanning trees if and only if it is (k,k)-tight.
By the Tutte-Nash-Williams theorem, the (k,k)-pebble game can be used to check whether a graph is an aborescence. With an extension of the pebble game called the pebble game with colors we can also find the trees. In the pebble game with colors, each of the k pebbles initially on a vertex has a different color.
As edges are added and pebbles are picked up, they are used to color the edges. With the appropriate rules for moving the pebbles and recoloring edges, each monochromatic subgraph remains acyclic.
The relationship between (k, l)-sparsity and tree decompositions is, by itself, an interesting theory, and recent work has also shown that these are intimately related to rigidity as well.
The concept of (k, l)-sparsity extends to hypergraphs. A hypergraph (or set system) is a given by a finite set of vertices and a set of hyperedges, which are non-empty subsets of the vertices. We call the vertices in a hyperedge its endpoints.
A hypergraph is (k, l)-sparse when any set of n' vertices spans at most kn'-l hyperedges. A set of vertices spans a hyperedge if it contains the hyperedge.
We extended the pebble game paradigm to sparse hypergraphs. Below is the pebble game for hypergraphs running on the faces of a tetrahedron.
Click on the section headings or arrows to open an close them. Java applets may load slowly the first time.