Audrey St. John |
## SparsityWe study problems for the combinatorial property ofsparsity. Let
k and l be non-negative integer parameters. A graph is
called (shortly, "sparse") if every subset of (k,l)-sparsen' 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 .
For the range where (k,l)-tightl 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! |