Abstract 3-Rigidity and Bivariate $C_2^1$-Splines I: Whiteley’s Maximality Conjecture

Abstract 3-Rigidity and Bivariate $C_2^1$-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 $x_1,\dots,x_n$ in $\mathbb R^d$ and the edge joining $x_i$ to $x_j$ to be the line segment with $x_i$ and $x_j$ 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 $\mathbb R^d$. 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 $K_4$ into $\mathbb R^3$ 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 $\mathcal I$ of subsets, which are called independent, that satisfy the following three axioms.

1. $\emptyset\in\mathcal I$. (This axiom is just to ensure the existence of an independent set.)
2. If $A\in\mathcal I$ and $B\subset A$, then $B\in\mathcal I$.
3. If $A,B\in\mathcal I$ and $|B|>|A|$, then there exists $x\in B$ such that $A\cup\{x\}\in\mathcal 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 $T_{ew}$ is 0 if $w$ is not one of the end points of $e$, and if $e$ is the edge $uv$, then $T_{eu}=u-v$ and $T_{ev}=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 $\mathbb R^d$, then this matroid is called the generic $d$-dimensional rigidity matroid of the graph, and is denoted by $\mathcal R_d(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 $K_n$, and moreover that it is the generic $d$-dimensional rigidity matroid of $K_n$. (Here the ordering is the so-called weak order, where if two matroids $M_1$ and $M_2$ have the same ground set, then $M_1\preceq M_2$ if every independent set in $M_1$ is an independent set in $M_2$.)

Graver proved this conjecture for $d=1,2$, and it has been shown to be false for $d\geq 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 $K_n$ 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 $C_{d-1}^{d-2}$-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 $C_2^1$-cofactor matroid of $K_n$ 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.