- Source: 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 property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.
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.
Definitions
(
k
,
l
)
{\displaystyle (k,l)}
-sparse multigraph. A multigraph
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
is
(
k
,
l
)
{\displaystyle (k,l)}
-sparse, where
k
{\displaystyle k}
and
l
{\displaystyle l}
are non-negative integers, if for every subgraph
G
′
=
(
V
′
,
E
′
)
{\displaystyle G'=(V',E')}
of
G
{\displaystyle G}
, we have
|
E
′
|
≤
k
|
V
′
|
−
l
{\displaystyle |E'|\leq k|V'|-l}
.
(
k
,
l
)
{\displaystyle (k,l)}
-tight multigraph. A multigraph
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
is
(
k
,
l
)
{\displaystyle (k,l)}
-tight if it is
(
k
,
l
)
{\displaystyle (k,l)}
-sparse and
|
E
|
=
k
|
V
|
−
l
{\displaystyle |E|=k|V|-l}
.
[
a
,
b
]
{\displaystyle [a,b]}
-sparse and tight multigraph. A multigraph
G
=
(
V
,
E
∪
F
)
{\displaystyle G=(V,E\cup F)}
is
[
a
,
b
]
{\displaystyle [a,b]}
-sparse if there exists a subset
F
′
⊂
F
{\displaystyle F'\subset F}
such that the subgraph
G
′
=
(
V
,
E
∪
F
′
)
{\displaystyle G'=(V,E\cup F')}
is
(
a
,
a
)
{\displaystyle (a,a)}
-sparse and the subgraph
G
″
=
(
V
,
F
∖
F
′
)
{\displaystyle G''=(V,F\setminus F')}
is
(
b
,
b
)
{\displaystyle (b,b)}
-sparse. The multigraph
G
{\displaystyle G}
is
[
a
,
b
]
{\displaystyle [a,b]}
-tight if, additionally,
|
E
∪
F
|
=
(
a
+
b
)
|
V
|
−
(
a
+
b
)
{\displaystyle |E\cup F|=(a+b)|V|-(a+b)}
.
(
k
,
l
)
{\displaystyle (k,l)}
-sparsity matroid. The
(
k
,
l
)
{\displaystyle (k,l)}
-sparsity matroid is a matroid whose ground set is the edge set of the complete multigraph on
n
{\displaystyle n}
vertices, with loop multiplicity
k
−
l
{\displaystyle k-l}
and edge multiplicity
2
k
−
l
{\displaystyle 2k-l}
, and whose independent sets are
(
k
,
l
)
{\displaystyle (k,l)}
-sparse multigraphs on
n
{\displaystyle n}
vertices. The bases of the matroid are the
(
k
,
l
)
{\displaystyle (k,l)}
-tight multigraphs and the circuits are the
(
k
,
l
)
{\displaystyle (k,l)}
-sparse multigraphs
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
that satisfy
|
E
|
=
k
|
V
|
−
l
+
1
{\displaystyle |E|=k|V|-l+1}
.
The first examples of sparsity matroids can be found in. Not all pairs
(
k
,
l
)
{\displaystyle (k,l)}
induce a matroid.
Pairs (k,l) that form a matroid
The following result provides sufficient restrictions on
(
k
,
l
)
{\displaystyle (k,l)}
for the existence of a matroid.
Theorem. The
(
k
,
l
)
{\displaystyle (k,l)}
-sparse multigraphs on
n
{\displaystyle n}
vertices are the independent sets of a matroid if
n
≥
1
{\displaystyle n\geq 1}
and
l
∈
[
0
,
k
]
{\displaystyle l\in [0,k]}
;
n
≥
2
{\displaystyle n\geq 2}
and
l
∈
(
k
,
3
2
k
)
{\displaystyle l\in (k,{\frac {3}{2}}k)}
; or
n
=
2
{\displaystyle n=2}
or
n
≥
l
2
k
−
l
{\displaystyle n\geq {\frac {l}{2k-l}}}
and
l
∈
[
3
2
k
,
2
k
)
{\displaystyle l\in [{\frac {3}{2}}k,2k)}
.
Some consequences of this theorem are that
(
2
,
3
)
{\displaystyle (2,3)}
-sparse multigraphs form a matroid while
(
3
,
6
)
{\displaystyle (3,6)}
-sparse multigraphs do not. Hence, the bases, i.e.,
(
2
,
3
)
{\displaystyle (2,3)}
-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
(
3
,
6
)
{\displaystyle (3,6)}
-sparse multigraphs will have different numbers of edges, and it is interesting to identify the one with the maximum number of edges.
Connections to rigidity and decomposition
Structural rigidity is about determining if almost all, i.e. generic, embeddings of a (simple or multi) graph in some
d
{\displaystyle d}
-dimensional metric space are rigid. 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.
Maxwell Direction. If a graph
G
{\displaystyle G}
is generically minimally rigid in
d
{\displaystyle d}
-dimensions, then it is independent in the
(
d
,
(
d
+
1
2
)
)
{\displaystyle \left(d,{d+1 \choose 2}\right)}
-sparsity matroid.
The converse of this theorem was proved in
2
{\displaystyle 2}
-dimensions, yielding a complete combinatorial characterization of generically rigid graphs in
R
2
{\displaystyle \mathbb {R} ^{2}}
. However, the converse is not true for
d
≥
3
{\displaystyle d\geq 3}
, 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. Let
k
G
{\displaystyle kG}
be the multigraph obtained by duplicating the edges of a multigraph
G
{\displaystyle G}
k
{\displaystyle k}
times.
The Tutte and Nash-Williams theorem shows that
(
k
,
k
)
{\displaystyle (k,k)}
-tight graphs are equivalent to graphs that can be decomposed into
k
{\displaystyle k}
edge-disjoint spanning trees, called
k
{\displaystyle k}
-arborescences. A
(
k
,
a
)
{\displaystyle (k,a)}
-arborescence is a multigraph
G
{\displaystyle G}
such that adding
a
{\displaystyle a}
edges to
G
{\displaystyle G}
yields a
k
{\displaystyle k}
-arborescence. For
l
∈
[
k
,
2
k
)
{\displaystyle l\in [k,2k)}
, a
(
k
,
l
)
{\displaystyle (k,l)}
-sparse multigraph is a
(
k
,
l
−
k
)
{\displaystyle (k,l-k)}
-arborescence; this was first shown for
(
2
,
3
)
{\displaystyle (2,3)}
sparse graphs. Additionally, many of the rigidity and sparsity results above can be written in terms of edge-disjoint spanning trees.
Constructing sparse multigraphs
This section gives methods to construct various sparse multigraphs using operations defined in constructing generically rigid graphs. Since these operations are defined for a given dimension, let a
(
k
,
0
)
{\displaystyle (k,0)}
-extension be a
k
{\displaystyle k}
-dimensional
0
{\displaystyle 0}
-extension, i.e., a
0
{\displaystyle 0}
-extension where the new vertex is connected to
k
{\displaystyle k}
distinct vertices. Likewise, a
(
k
,
1
)
{\displaystyle (k,1)}
-extension is a
k
{\displaystyle k}
-dimensional
1
{\displaystyle 1}
-extension.
General (k,l)-sparse multigraphs
The first construction is for
(
k
,
k
)
{\displaystyle \left(k,k\right)}
-tight graphs. A generalized
(
k
,
1
)
{\displaystyle (k,1)}
-extension is a triple
(
k
,
1
,
j
)
{\displaystyle (k,1,j)}
, where
j
{\displaystyle j}
edges are removed, for
1
≤
j
≤
k
{\displaystyle 1\leq j\leq k}
, and the new vertex
u
{\displaystyle u}
is connected to the vertices of these
j
{\displaystyle j}
edges and to
k
−
j
{\displaystyle k-j}
distinct vertices. The usual
(
k
,
1
)
{\displaystyle (k,1)}
-extension is a
(
k
,
1
,
1
)
{\displaystyle (k,1,1)}
-extension.
Theorem. A multigraph is
(
k
,
k
)
{\displaystyle (k,k)}
-tight if and only if it can be constructed from a single vertex via a sequence of
(
k
,
0
)
{\displaystyle (k,0)}
- and
(
k
,
1
,
j
)
{\displaystyle (k,1,j)}
-extensions.
This theorem was then extended to general
(
k
,
l
)
{\displaystyle (k,l)}
-tight graphs. Consider another generalization of a
1
{\displaystyle 1}
-extension denoted by
(
k
,
1
,
i
,
j
)
{\displaystyle (k,1,i,j)}
, for
0
≤
j
≤
i
≤
k
{\displaystyle 0\leq j\leq i\leq k}
, where
j
{\displaystyle j}
edges are removed, the new vertex
u
{\displaystyle u}
is connected to the vertices of these
j
{\displaystyle j}
edges,
i
−
j
{\displaystyle i-j}
loops are added to
u
{\displaystyle u}
, and
u
{\displaystyle u}
is connected to
k
−
i
{\displaystyle k-i}
other distinct vertices. Also, let
P
l
{\displaystyle P_{l}}
denote a multigraph with a single node and
l
{\displaystyle l}
loops.
Theorem. A multigraph
G
{\displaystyle G}
is
(
k
,
l
)
{\displaystyle (k,l)}
-tight for
l
∈
[
1
,
k
]
{\displaystyle l\in [1,k]}
if and only if
G
{\displaystyle G}
can be constructed from
P
k
−
l
{\displaystyle P_{k-l}}
via a sequence of
(
k
,
1
,
i
,
j
)
{\displaystyle (k,1,i,j)}
-extensions, such that
0
≤
j
≤
i
≤
k
−
1
{\displaystyle 0\leq j\leq i\leq k-1}
and
i
−
j
≤
k
−
l
{\displaystyle i-j\leq k-l}
;
l
=
0
{\displaystyle l=0}
if and only if
G
{\displaystyle G}
can be constructed from
P
k
−
l
{\displaystyle P_{k-l}}
via a sequence of
(
k
,
1
,
i
,
j
)
{\displaystyle (k,1,i,j)}
-extensions, such that
0
≤
j
≤
i
≤
k
{\displaystyle 0\leq j\leq i\leq k}
and
i
−
j
≤
k
−
l
{\displaystyle i-j\leq k-l}
.
Neither of these constructions are sufficient when the graph is simple. The next results are for
(
k
,
l
)
{\displaystyle (k,l)}
-sparse hypergraphs. A hypergraph is
s
{\displaystyle s}
-uniform if each of its edges contains exactly
s
{\displaystyle s}
vertices. First, conditions are established for the existence of
(
k
,
l
)
{\displaystyle (k,l)}
-tight hypergraphs.
Theorem. There exists an
n
0
{\displaystyle n_{0}}
such that for all
n
≥
n
0
{\displaystyle n\geq n_{0}}
, there exist
s
{\displaystyle s}
-uniform hypergraphs on
n
{\displaystyle n}
vertices that are
(
k
,
l
)
{\displaystyle (k,l)}
-tight.
The next result extends the Tutte and Nash-Williams theorem to hypergraphs.
Theorem. If
G
{\displaystyle G}
is a
(
k
,
l
)
{\displaystyle (k,l)}
-tight hypergraph, for
l
≥
k
{\displaystyle l\geq k}
, then
G
{\displaystyle G}
is a
(
k
,
l
−
k
)
{\displaystyle (k,l-k)}
arborescence, where the
l
−
k
{\displaystyle l-k}
added edges contain at least two vertices.
A map-hypergraph is a hypergraph that admits an orientation such that each vertex has an out-degree of
1
{\displaystyle 1}
. A
k
{\displaystyle k}
-map-hypergraph is a map-hypergraph that can be decomposed into
k
{\displaystyle k}
edge-disjoint map-hypergraphs.
Theorem. If
G
{\displaystyle G}
is a
(
k
,
l
)
{\displaystyle (k,l)}
-tight hypergraph, for
k
≥
l
{\displaystyle k\geq l}
, then
g
{\displaystyle g}
is the union of an
l
{\displaystyle l}
-arborescence and a
(
k
−
l
)
{\displaystyle (k-l)}
-map-hypergraph.
(2,3)-sparse graphs
The first result shows that
(
2
,
3
)
{\displaystyle (2,3)}
-tight graphs, i.e., generically minimally rigid graphs in
R
2
{\displaystyle \mathbb {R} ^{2}}
have Henneberg-constructions.
Theorem. A graph
G
{\displaystyle G}
is
(
2
,
3
)
{\displaystyle (2,3)}
-tight if and only if it can be constructed from the complete graph
K
2
{\displaystyle K_{2}}
via a sequence of
0
{\displaystyle 0}
- and
1
{\displaystyle 1}
-extensions.
The next result shows how to construct
(
2
,
3
)
{\displaystyle (2,3)}
-circuits. In this setting, a
2
{\displaystyle 2}
-sum combines two graphs by identifying two
K
2
{\displaystyle K_{2}}
subgraphs in each and then removing the combined edge from the resulting graph.
Theorem. A graph
G
{\displaystyle G}
is a
(
2
,
3
)
{\displaystyle (2,3)}
-circuit if and only if it can be constructed from disjoint copies of the complete graph
K
4
{\displaystyle K_{4}}
via a sequence of
1
{\displaystyle 1}
-extensions within connected components and
2
{\displaystyle 2}
-sums of connected components.
The method for constructing
3
{\displaystyle 3}
-connected
(
2
,
3
)
{\displaystyle (2,3)}
-circuits is even simpler.
Theorem. A graph
G
{\displaystyle G}
is a
3
{\displaystyle 3}
-connected
(
2
,
3
)
{\displaystyle (2,3)}
-circuit if and only if it can be constructed from the complete graph
K
4
{\displaystyle K_{4}}
via a sequence of
1
{\displaystyle 1}
-extensions.
These circuits also have the following combinatorial property.
Theorem. If a graph
G
{\displaystyle G}
is a
(
2
,
3
)
{\displaystyle (2,3)}
-circuit that is not the complete graph
K
4
{\displaystyle K_{4}}
, then
G
{\displaystyle G}
has at least
3
{\displaystyle 3}
vertices of degree
3
{\displaystyle 3}
such that performing a
1
{\displaystyle 1}
-reduction on any one of these vertices yields another
(
2
,
3
)
{\displaystyle (2,3)}
-circuit.
(2,2)-sparse graphs
The next results shows how to construct
(
2
,
2
)
{\displaystyle (2,2)}
-circuits using two different construction methods. For the first method, the base graphs are shown in Figure 2 and the three join operations are shows in Figure 2. A
1
{\displaystyle 1}
-join identifies a
K
2
{\displaystyle K_{2}}
subgraph in
G
1
{\displaystyle G_{1}}
with an edge of a
K
4
{\displaystyle K_{4}}
subgraph in
G
1
{\displaystyle G_{1}}
, and removes the other two vertices of the
K
4
{\displaystyle K_{4}}
. A
2
{\displaystyle 2}
-join identifies an edge of a
K
4
{\displaystyle K_{4}}
subgraph in
G
1
{\displaystyle G_{1}}
with an edge of a
K
4
{\displaystyle K_{4}}
subgraph in
G
2
{\displaystyle G_{2}}
, and removes the other vertices on both
K
4
{\displaystyle K_{4}}
subgraphs. A
3
{\displaystyle 3}
-join takes a degree
3
{\displaystyle 3}
vertex
v
1
{\displaystyle v_{1}}
in
G
1
{\displaystyle G_{1}}
and a degree
3
{\displaystyle 3}
vertex
v
2
{\displaystyle v_{2}}
in
G
2
{\displaystyle G_{2}}
and removes them, then it adds
3
{\displaystyle 3}
edges between
G
1
{\displaystyle G_{1}}
and
G
2
{\displaystyle G_{2}}
such that there is a bijection between the neighbors of
v
1
{\displaystyle v_{1}}
and
v
2
{\displaystyle v_{2}}
.
The second method uses
2
{\displaystyle 2}
-dimensional vertex-splitting, defined in the constructing generically rigid graphs, and a vertex-to-
K
4
{\displaystyle K_{4}}
operation, which replace a vertex
v
{\displaystyle v}
of a graph with a
K
4
{\displaystyle K_{4}}
graph and connects each neighbor of
v
{\displaystyle v}
to any vertex of the
K
4
{\displaystyle K_{4}}
.
Theorem. A graph
G
{\displaystyle G}
is a
(
2
,
2
)
{\displaystyle (2,2)}
-circuit if and only if
G
{\displaystyle G}
can be constructed from disjoint copies of the base graphs via a sequence of
1
{\displaystyle 1}
-extensions within connected components and
1
{\displaystyle 1}
-,
2
{\displaystyle 2}
-, and
3
{\displaystyle 3}
- sums of connected components;
G
{\displaystyle G}
can be constructed from
K
4
{\displaystyle K_{4}}
via a sequence of
0
{\displaystyle 0}
- and
1
{\displaystyle 1}
-extensions, vertex-to-
K
4
{\displaystyle K_{4}}
, and
2
{\displaystyle 2}
-dimensional vertex-splitting operations
(2,1)-sparse graphs
The following result gives a construction method for
(
2
,
1
)
{\displaystyle (2,1)}
-tight graphs and extends the Tutte and Nash-Williams theorem to these graphs. For the construction, the base graphs are
K
5
{\displaystyle K_{5}}
with an edge removed or the
2
{\displaystyle 2}
-sum of two
K
4
{\displaystyle K_{4}}
graphs (the shared edge is not removed), see the middle graph in Figure 2. Also, an edge-joining operation adds a single edge between two graphs.
Theorem. A graph
G
{\displaystyle G}
is
(
2
,
1
)
{\displaystyle (2,1)}
-tight if and only if
G
{\displaystyle G}
can be obtained from
K
5
{\displaystyle K_{5}}
with an edge removed or the
2
{\displaystyle 2}
-sum of two
K
4
{\displaystyle K_{4}}
graphs via a sequence of
0
{\displaystyle 0}
- and
1
{\displaystyle 1}
-extensions, vertex-to-
K
4
{\displaystyle K_{4}}
,
2
{\displaystyle 2}
-dimensional vertex-splitting, and edge-joining operations;
G
{\displaystyle G}
is the edge-disjoint union of a spanning tree and a spanning graph in which every connected component contains exactly one cycle.
Pebble games
There is a family of efficient network-flow based algorithms for identifying
(
k
,
l
)
{\displaystyle (k,l)}
-sparse graphs, where
l
∈
[
0
,
2
k
]
{\displaystyle l\in [0,2k]}
. The first of these types of algorithms was for
(
2
,
3
)
{\displaystyle (2,3)}
-sparse graphs. These algorithms are explained on the Pebble game page.
References
Kata Kunci Pencarian:
- Sparsity matroid
- Paving matroid
- Matroid girth
- Rigidity matroid
- Geiringer–Laman theorem
- Outline of combinatorics
- Spark (mathematics)
- Branch-decomposition
- Pseudoforest
- Girth (graph theory)
