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 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!