Processing math: 100%
Discrete Analysis
Analysis of Boolean functions
Analysis on graphs
Analytic Combinatorics
Arithmetic Combinatorics
Combinatorial Geometry
Extremal combinatorics
Geometric Measure Theory
Metric Geometry
Probabilistic Combinatorics
https://discreteanalysisjournal.com/feed
April 22, 2022 BST
Abstract 3-Rigidity and Bivariate C12-Splines I: Whiteley's Maximality Conjecture
Katie Clinch
Bill Jackson
School of Mathematical Sciences, Queen Mary University of London
More about Bill Jackson
Shin-ichi Tanigawa
Department of Mathematical Informatics, University of Tokyo
More about Shin-ichi Tanigawa
https://doi.org/10.19086/da.34691
cofactor matroid bivariate spline abstract rigidity matroid graph rigidity math.co (mathematics - combinatorics)
Copyright Logoccby-4.0
Photo by Soroush Karimi on Unsplash
Editorial introduction
Read article at ArXiv
Abstract 3-Rigidity and Bivariate C12-Splines I: Whiteley's Maximality Conjecture, Discrete Analysis 2022:2, 50 pp.
Suppose one realizes a graph G by taking its vertex set to be a set of points x1,…,xn in Rd and the edge joining xi to xj to be the line segment with xi and xj as its endpoints. Now imagine that these edges are made out of steel rods, so the embedded graph forms a kind of scaffolding structure. This structure is called rigid if the only way of moving it is to rotate or translate the entire structure in Rd. Another way to put it is that the lengths of the edges – that is, the distances between neighbouring vertices in the graph – locally determine the graph up to congruence. The word "locally" here is important: there may be more than one way of embedding a graph with the given distances, but the embedding is nevertheless rigid if it is not possible to move continuously from it to a non-congruent embedding.
For some simple examples, an embedding of the complete graph K4 into R3 as a regular tetrahedron is rigid, whereas embedding a cube in the obvious way with the vertex set {0,1}3 is not.
Rigidity is a much studied topic, and one soon finds that in order to answer questions about it, one is forced to look in more detail at the dependences between different parts of a structure, and the degrees of freedom that they enjoy. For example, two tetrahedra joined at a vertex quite clearly split into two rigid parts whose relative motion is restricted to be a rotation about the common vertex.
Many of the properties of an embedded graph are encapsulated by an object known as its rigidity matroid. Recall that matroid theory is an abstraction of the notion of linear independence in vector spaces. A matroid M is a set X together with a collection I of subsets, which are called independent, that satisfy the following three axioms.
∅∈I. (This axiom is just to ensure the existence of an independent set.)
If A∈I and B⊂A, then B∈I.
If A,B∈I and |B|>|A|, then there exists x∈B such that A∪{x}∈I.
The third axiom is of course the important one: it is called the exchange axiom, and it allows one to define the dimension of a matroid to be the size of any maximal independent set. The rank of a subset of a matroid is also defined to be the size of the largest independent set it contains.
Informally, the rigidity matroid of an embedded graph G takes X to be the set of edges of G, with a collection A of edges deemed to be independent if the removal of any edge from the subgraph with edge set A increases the degrees of freedom of this subgraph. Equivalently, the constraints imposed by any of the edges of A are not implied by the constraints imposed by the other edges. Formally, one takes the vector-valued matrix T indexed by the edges and vertices where the entry Tew is 0 if w is not one of the end points of e, and if e is the edge uv, then Teu=u−v and Tev=v−u. This matrix is called the rigidity matrix of the embedding, and the independent sets of edges in the rigidity matroid are those that give rise to independent sets of rows in the rigidity matrix.
A useful observation is that provided the embedded vertices are sufficiently generic – it suffices, for instance, if all their coordinates are algebraically independent – then the rigidity matroid depends only on the graph and not on the embedding. If the embedding is into Rd, then this matroid is called the generic d-dimensional rigidity matroid of the graph, and is denoted by Rd(G).
Since the complete graph on n vertices contains all other graphs on n vertices, attention naturally turns to the generic d-dimensional rigidity matroids of complete graphs. These are well understood for d=1,2, but it is a major open problem to describe them combinatorially for d=3.
An interesting slant on the problem was introduced by Jack Graver, who defined a notion of an abstract rigidity matroid. This was based on the observation that rigidity matroids satisfy two simple properties (explained on page 2 of the paper), so one can take these two properties to be the definition of an abstract d-dimensional rigidity matroid. Graver then conjectured that for each d and n there is a unique maximal abstract d-dimensional rigidity matroid on the edges of Kn, and moreover that it is the generic d-dimensional rigidity matroid of Kn. (Here the ordering is the so-called weak order, where if two matroids M1 and M2 have the same ground set, then M1⪯M2 if every independent set in M1 is an independent set in M2.)
Graver proved this conjecture for d=1,2, and it has been shown to be false for d≥4, but for d=3 it is still an open problem. However, this paper takes a significant step by proving at least the first part: there is a unique maximal 3-dimensional rigidity matroid on Kn for each n. It achieves this by proving the d=3 case of a 1996 conjecture of Walter Whiteley, which replaces the generic d-dimensional rigidity matroid in Graver's conjecture by another matroid called the generic Cd−2d−1-cofactor matroid (defined in the paper). This is already an important step in our understanding of 3-dimensional rigidity matroids. To complete the proof of Graver's conjecture when d=3 it would be necessary to prove that the generic C12-cofactor matroid of Kn and the generic 3-dimensional rigidity matroid coincide.
Here is a general introduction to rigidity by the second author, followed by a talk on the results of this paper.