Pebble games for Sparse Graphs

Sparse graphs:

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.

(k, l)-pebble games:

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.

Initial configuration

Each vertex starts with k pebbles on it, and there are no edges.

Add edge move

If i and j are vertices with at least l+1 pebbles between them, add the edge ij (oriented toward j) and pick up one of the pebbles from i.

Pebble slide move

If ij is an edge in the pebble game's graph and there is a pebble on j, reverse ij and move the pebble from j to i.

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.

Theorem:

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.

Sparsity and arboricity:

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.)

Theorem (Nash-Williams-Tutte):

A graph admits a decomposition into k edge-disjoint spanning trees if and only if it is (k,k)-tight.

The pebble game with colors:

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.

Sparse hypergraphs:

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.

The pebble game for sparse hypergrpahs:

We extended the pebble game paradigm to sparse hypergraphs. Below is the pebble game for hypergraphs running on the faces of a tetrahedron.