|Audrey St. John||
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
- 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!