 Audrey St. John

### Sparsity

We study problems for the combinatorial property of sparsity. Let k and l be non-negative integer parameters. A graph is called (k,l)-sparse (shortly, "sparse") if every subset of n' vertices spans at most kn' - l edges (for large enough values of n' that do not make this a negative value). If, furthermore, the graph has exactly kn - l edges overall, we call the graph (k,l)-tight. For the range where l is contained in [0, 2k), sparse graphs are matroidal and a family of algorithms called the pebble games have been developed to solve the following fundamental sparsity problems:
• Decision problem: Is a graph (k,l)-sparse? tight?
• Spanning problem: Does a graph span a (k,l)-tight subgraph?
• Extraction problem: Extract a maximum-sized subgraph (with respect to vertices) that is sparse.
• Optimization problem: Given an arbitrary weight function on the edges of a graph, extract a sparse subgraph of maximum weight.
• Components problem: Given a sparse graph that is not tight, detect its components, or maximal (with respect to vertices) subgraphs that are themselves spanning.
• Redundancy problem: Is a spanning graph redundantly spanning? That is, does the removal of any edge leave the graph spanning? (This is analogous to redundantly rigid.)
• Henneberg problem: Given a tight graph, determine an inductive construction of it using simple rules at each step.

#### Examples of sparsity

• (1,1)-sparsity is equivalent to the graphic matroid
• [Nash-Williams, Tutte](k,k)-tight graphs are (k,k)-arborescences: those graphs which are the edge-disjoint union of k spanning trees
• [Haas](k,l+a)-tight graphs are associated with (k,a)-arborescences: those graphs such that the addition of any a edges results in a (k,k)-arborescence.
• [Laman](2,3)-tight graphs are minimally rigid bar-and-joint graphs in the plane
• [Tay](6,6)-tight graphs are associated with minimally rigid body-and-bar graphs in 3-space (note that this characterization generalizes to arbitrary dimension d).

More definitions and examples coming soon!