Sparsity matroid
A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges.
To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph.
The graphs we are concerned with generalise simple directed graphs by allowing multiple same-oriented edges between pairs of vertices.
Matroids are a quite general mathematical abstraction that describe the amount of indepdendence in, variously, points in geometric space and paths in a graph; when applied to characterising sparsity, matroids describe certain sets of sparse graphs.
These matroids are connected to the structural rigidity of graphs and their ability to be decomposed into edge-disjoint spanning trees via the Tutte and Nash-Williams theorem.
There is a family of efficient algorithms, known as pebble games, for determining if a multigraph meets the given sparsity condition.
The first examples of sparsity matroids can be found in.
vertices are the independent sets of a matroid if Some consequences of this theorem are that
-tight multigraphs, must all have the same number of edges and can be constructed using techniques discussed below.
On the other hand, without this matroidal structure, maximally
Structural rigidity is about determining if almost all, i.e. generic, embeddings of a (simple or multi) graph in some
More precisely, this theory gives combinatorial characterizations of such graphs.
In Euclidean space, Maxwell showed that independence in a sparsity matroid is necessary for a graph to be generically rigid in any dimension.
-dimensions, yielding a complete combinatorial characterization of generically rigid graphs in
, see combinatorial characterizations of generically rigid graphs.
Other sparsity matroids have been used to give combinatorial characterizations of generically rigid multigraphs for various types of frameworks, see rigidity for other types of frameworks.
The following table summarizes these results by stating the type of generic rigid framework in a given dimension and the equivalent sparsity condition.
[14][15] Additionally, many of the rigidity and sparsity results above can be written in terms of edge-disjoint spanning trees.
This section gives methods to construct various sparse multigraphs using operations defined in constructing generically rigid graphs.
-tight if and only if it can be constructed from a single vertex via a sequence of
denote a multigraph with a single node and
The next result extends the Tutte and Nash-Williams theorem to hypergraphs.
A map-hypergraph is a hypergraph that admits an orientation such that each vertex has an out-degree of
subgraphs in each and then removing the combined edge from the resulting graph.
-circuit if and only if it can be constructed from disjoint copies of the complete graph
-dimensional vertex-splitting, defined in the constructing generically rigid graphs, and a vertex-to-
-circuit if and only if The following result gives a construction method for
Also, an edge-joining operation adds a single edge between two graphs.
-tight if and only if There is a family of efficient network-flow based algorithms for identifying
These algorithms are explained on the Pebble game page.
