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

edit

 -sparse multigraph. [1] A multigraph   is  -sparse, where   and   are non-negative integers, if for every subgraph   of  , we have  .

 -tight multigraph. [1] A multigraph   is  -tight if it is  -sparse and  .

 -sparse and tight multigraph. [2] A multigraph   is  -sparse if there exists a subset   such that the subgraph   is  -sparse and the subgraph   is  -sparse. The multigraph   is  -tight if, additionally,  .

 -sparsity matroid. [1] The  -sparsity matroid is a matroid whose ground set is the edge set of the complete multigraph on   vertices, with loop multiplicity   and edge multiplicity  , and whose independent sets are  -sparse multigraphs on   vertices. The bases of the matroid are the  -tight multigraphs and the circuits are the  -sparse multigraphs   that satisfy  .

The first examples of sparsity matroids can be found in.[3] Not all pairs   induce a matroid.

Pairs (k,l) that form a matroid

edit

The following result provides sufficient restrictions on   for the existence of a matroid.

Theorem. [1] The  -sparse multigraphs on   vertices are the independent sets of a matroid if

  •   and  ;
  •   and  ; or
  •   or   and  .

Some consequences of this theorem are that  -sparse multigraphs form a matroid while  -sparse multigraphs do not. Hence, the bases, i.e.,  -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  -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

edit

Structural rigidity is about determining if almost all, i.e. generic, embeddings of a (simple or multi) graph in some  -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. [4] If a graph   is generically minimally rigid in  -dimensions, then it is independent in the  -sparsity matroid.

The converse of this theorem was proved in  -dimensions, yielding a complete combinatorial characterization of generically rigid graphs in  . However, the converse is not true for  , 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   be the multigraph obtained by duplicating the edges of a multigraph     times.

Generic minimally rigid framework Sparsity condition
Bar-joint framework in    -tight[5][6]
Bar-joint framework in   under general polyhedral norms  -tight[7]
Body-bar framework in    -tight[8]
 -plate-bar framework in    -tight[9][10]
Body-hinge framework in     is  -tight[9][10][11]
Body-cad framework in   primitive cad graph is  -tight[12]
Body-cad framework with no coincident points in   primitive cad graph is  -tight[12]

The Tutte and Nash-Williams theorem shows that  -tight graphs are equivalent to graphs that can be decomposed into   edge-disjoint spanning trees, called  -arborescences. A  -arborescence is a multigraph   such that adding   edges to   yields a  -arborescence. For  , a  -sparse multigraph is a  -arborescence;[13] this was first shown for   sparse graphs.[14][15] Additionally, many of the rigidity and sparsity results above can be written in terms of edge-disjoint spanning trees.

Constructing sparse multigraphs

edit

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  -extension be a  -dimensional  -extension, i.e., a  -extension where the new vertex is connected to   distinct vertices. Likewise, a  -extension is a  -dimensional  -extension.

General (k,l)-sparse multigraphs

edit

The first construction is for  -tight graphs. A generalized  -extension is a triple  , where   edges are removed, for  , and the new vertex   is connected to the vertices of these   edges and to   distinct vertices. The usual  -extension is a  -extension.

Theorem. [16] A multigraph is  -tight if and only if it can be constructed from a single vertex via a sequence of  - and  -extensions.

This theorem was then extended to general  -tight graphs. Consider another generalization of a  -extension denoted by  , for  , where   edges are removed, the new vertex   is connected to the vertices of these   edges,   loops are added to  , and   is connected to   other distinct vertices. Also, let   denote a multigraph with a single node and   loops.

Theorem. [17] A multigraph   is  -tight for

  •   if and only if   can be constructed from   via a sequence of  -extensions, such that   and  ;
  •   if and only if   can be constructed from   via a sequence of  -extensions, such that   and  .

Neither of these constructions are sufficient when the graph is simple.[18] The next results are for  -sparse hypergraphs. A hypergraph is  -uniform if each of its edges contains exactly   vertices. First, conditions are established for the existence of  -tight hypergraphs.

Theorem. [19] There exists an   such that for all  , there exist  -uniform hypergraphs on   vertices that are  -tight.

The next result extends the Tutte and Nash-Williams theorem to hypergraphs.

Theorem. [19] If   is a  -tight hypergraph, for  , then   is a   arborescence, where the   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  . A  -map-hypergraph is a map-hypergraph that can be decomposed into   edge-disjoint map-hypergraphs.

Theorem. [19] If   is a  -tight hypergraph, for  , then   is the union of an  -arborescence and a  -map-hypergraph.

(2,3)-sparse graphs

edit
 
Figure 1. A  -circuit.

The first result shows that  -tight graphs, i.e., generically minimally rigid graphs in   have Henneberg-constructions.

Theorem. [6][20] A graph   is  -tight if and only if it can be constructed from the complete graph   via a sequence of  - and  -extensions.

The next result shows how to construct  -circuits. In this setting, a  -sum combines two graphs by identifying two   subgraphs in each and then removing the combined edge from the resulting graph.

Theorem. [21] A graph   is a  -circuit if and only if it can be constructed from disjoint copies of the complete graph   via a sequence of  -extensions within connected components and  -sums of connected components.

The method for constructing  -connected  -circuits is even simpler.

Theorem. [21] A graph   is a  -connected  -circuit if and only if it can be constructed from the complete graph   via a sequence of  -extensions.

These circuits also have the following combinatorial property.

Theorem. [21] If a graph   is a  -circuit that is not the complete graph  , then   has at least   vertices of degree   such that performing a  -reduction on any one of these vertices yields another  -circuit.

(2,2)-sparse graphs

edit

The next results shows how to construct  -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  -join identifies a   subgraph in   with an edge of a   subgraph in  , and removes the other two vertices of the  . A  -join identifies an edge of a   subgraph in   with an edge of a   subgraph in  , and removes the other vertices on both   subgraphs. A  -join takes a degree   vertex   in   and a degree   vertex   in   and removes them, then it adds   edges between   and   such that there is a bijection between the neighbors of   and  .

 
Figure 2. The base graphs for constructing  -circuits.
 
Figure 3. From top to bottom, the  -,  -, and  -join operations for constructing  -circuits.

The second method uses  -dimensional vertex-splitting, defined in the constructing generically rigid graphs, and a vertex-to-  operation, which replace a vertex   of a graph with a   graph and connects each neighbor of   to any vertex of the  . Theorem. A graph   is a  -circuit if and only if

  •   can be constructed from disjoint copies of the base graphs via a sequence of  -extensions within connected components and  -,  -, and  - sums of connected components;[18]
  •  
    Figure 4. A  -circuit.
      can be constructed from   via a sequence of  - and  -extensions, vertex-to- , and  -dimensional vertex-splitting operations[22]

(2,1)-sparse graphs

edit

The following result gives a construction method for  -tight graphs and extends the Tutte and Nash-Williams theorem to these graphs. For the construction, the base graphs are   with an edge removed or the  -sum of two   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. [22] A graph   is  -tight if and only if

  •   can be obtained from   with an edge removed or the  -sum of two   graphs via a sequence of  - and  -extensions, vertex-to- ,  -dimensional vertex-splitting, and edge-joining operations;
  •   is the edge-disjoint union of a spanning tree and a spanning graph in which every connected component contains exactly one cycle.

Pebble games

edit

There is a family of efficient network-flow based algorithms for identifying  -sparse graphs, where  .[1] The first of these types of algorithms was for  -sparse graphs. These algorithms are explained on the Pebble game page.

References

edit
  1. ^ a b c d e Lee, Audrey; Streinu, Ileana (2008-04-28). "Pebble game algorithms and sparse graphs". Discrete Mathematics. 308 (8): 1425–1437. arXiv:math/0702129. doi:10.1016/j.disc.2007.07.104. ISSN 0012-365X. S2CID 2826.
  2. ^ Haller, Kirk; Lee-St.John, Audrey; Sitharam, Meera; Streinu, Ileana; White, Neil (2012-10-01). "Body-and-cad geometric constraint systems". Computational Geometry. 45 (8): 385–405. arXiv:1006.1126. doi:10.1016/j.comgeo.2010.06.003. ISSN 0925-7721.
  3. ^ Lorea, M. (1979-01-01). "On matroidal families". Discrete Mathematics. 28 (1): 103–106. doi:10.1016/0012-365X(79)90190-0. ISSN 0012-365X.
  4. ^ F.R.S, J. Clerk Maxwell (1864-04-01). "XLV. On reciprocal figures and diagrams of forces". The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 27 (182): 250–261. doi:10.1080/14786446408643663. ISSN 1941-5982.
  5. ^ Pollaczek‐Geiringer, H. (1927). "Über die Gliederung ebener Fachwerke". Zeitschrift für Angewandte Mathematik und Mechanik. 7 (1): 58–72. Bibcode:1927ZaMM....7...58P. doi:10.1002/zamm.19270070107. ISSN 1521-4001.
  6. ^ a b Laman, G. (1970-10-01). "On graphs and rigidity of plane skeletal structures". Journal of Engineering Mathematics. 4 (4): 331–340. Bibcode:1970JEnMa...4..331L. doi:10.1007/BF01534980. ISSN 1573-2703. S2CID 122631794.
  7. ^ Kitson, Derek (2015-09-01). "Finite and Infinitesimal Rigidity with Polyhedral Norms". Discrete & Computational Geometry. 54 (2): 390–411. arXiv:1401.1336. doi:10.1007/s00454-015-9706-x. ISSN 1432-0444. S2CID 15520982.
  8. ^ Tay, Tiong-Seng (1984-02-01). "Rigidity of multi-graphs. I. Linking rigid bodies in n-space". Journal of Combinatorial Theory. Series B. 36 (1): 95–112. doi:10.1016/0095-8956(84)90016-9. ISSN 0095-8956.
  9. ^ a b Tay, Tiong-Seng (1991-09-01). "Linking (n − 2)-dimensional panels inn-space I: (k − 1,k)-graphs and (k − 1,k)-frames". Graphs and Combinatorics. 7 (3): 289–304. doi:10.1007/BF01787636. ISSN 1435-5914. S2CID 40089590.
  10. ^ a b Tay, Tiong-Seng (1989-12-01). "Linking (n − 2)-dimensional panels inn-space II: (n − 2, 2)-frameworks and body and hinge structures". Graphs and Combinatorics. 5 (1): 245–273. doi:10.1007/BF01788678. ISSN 1435-5914. S2CID 8154653.
  11. ^ Whiteley, Walter (1988-05-01). "The Union of Matroids and the Rigidity of Frameworks". SIAM Journal on Discrete Mathematics. 1 (2): 237–255. doi:10.1137/0401025. ISSN 0895-4801.
  12. ^ a b Lee-St.John, Audrey; Sidman, Jessica (2013-02-01). "Combinatorics and the rigidity of CAD systems". Computer-Aided Design. Solid and Physical Modeling 2012. 45 (2): 473–482. arXiv:1210.0451. doi:10.1016/j.cad.2012.10.030. ISSN 0010-4485. S2CID 14851683.
  13. ^ Haas, Ruth (2002). "Characterizations of arboricity of graphs". Ars Combinatoria. 63.
  14. ^ Lovász, L.; Yemini, Y. (1982-03-01). "On Generic Rigidity in the Plane". SIAM Journal on Algebraic and Discrete Methods. 3 (1): 91–98. doi:10.1137/0603009. ISSN 0196-5212.
  15. ^ Recski, András (1984-03-01). "A network theory approach to the rigidity of skeletal structures Part I. Modelling and interconnection". Discrete Applied Mathematics. 7 (3): 313–324. doi:10.1016/0166-218X(84)90007-6. ISSN 0166-218X.
  16. ^ Tay, Tiong-Seng (1991). "Henneberg's Method for Bar and Body Frameworks". Structural Topology. ISSN 0226-9171.
  17. ^ Fekete, Zsolt; Szegő, László (2007), Bondy, Adrian; Fonlupt, Jean; Fouquet, Jean-Luc; Fournier, Jean-Claude (eds.), "A Note on [k, l]-sparse Graphs", Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics, Basel: Birkhäuser, pp. 169–177, doi:10.1007/978-3-7643-7400-6_13, ISBN 978-3-7643-7400-6, retrieved 2021-01-22
  18. ^ a b Nixon, Anthony (2014-11-01). "A constructive characterisation of circuits in the simple (2,2)-sparsity matroid". European Journal of Combinatorics. 42: 92–106. doi:10.1016/j.ejc.2014.05.009. ISSN 0195-6698. S2CID 1419117.
  19. ^ a b c Streinu, Ileana; Theran, Louis (2009-11-01). "Sparse hypergraphs and pebble game algorithms". European Journal of Combinatorics. 30 (8): 1944–1964. doi:10.1016/j.ejc.2008.12.018. ISSN 0195-6698. S2CID 5477763.
  20. ^ Henneberg, I. (1908), "Die Graphische Statik der Starren Körper", Encyklopädie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Wiesbaden: Vieweg+Teubner Verlag, pp. 345–434, doi:10.1007/978-3-663-16021-2_5, ISBN 978-3-663-15450-1, retrieved 2021-01-22
  21. ^ a b c Berg, Alex R.; Jordán, Tibor (2003-05-01). "A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid". Journal of Combinatorial Theory. Series B. 88 (1): 77–97. doi:10.1016/S0095-8956(02)00037-0. ISSN 0095-8956.
  22. ^ a b Nixon, Anthony; Owen, John (2014-12-30). "An inductive construction of $(2,1)$-tight graphs". Contributions to Discrete Mathematics. 9 (2). doi:10.11575/cdm.v9i2.62096. ISSN 1715-0868. S2CID 35739977.