Abstract 3-Rigidity and Bivariate $C_2^1$-Splines II: Combinatorial Characterization

Abstract 3-Rigidity and Bivariate $C_2^1$-Splines II: Combinatorial Characterization, Discrete Analysis 2022:3, 32 pp.

As its title suggests, this paper follows on from the previous paper published in this journal. Likewise, to understand this editorial introduction, it will help to have read the previous one.

As explained there, the rigidity matroid of an arrangement of rods in $\mathbb R^d$ is the matroid in which the elements are the rods, with a set of rods deemed to be independent if the removal of any one of them increases the degrees of freedom of the structure. It turns out that if all the coordinates of the end-points of the rods, which are vertices of a geometric graph, are algebraically independent, then the rigidity matroid depends only on the graph and not on the choice of vertices and lengths of the rods. The resulting matroid is called the generic $d$-dimensional rigidity matroid of the graph. The generic $d$-dimensional rigidity matroid of a graph $G$ is denoted by $\mathcal R_d(G)$.

The matroid $\mathcal R_d(K_n)$ is particularly important, since a full description of this matroid will include descriptions of $\mathcal R_d(G)$ for all graphs on $n$ vertices. However, understanding these matroids combinatorially is a challenging open problem.

An advance on the problem was made by Graver, who defined a family of matroids on the edge set of $K_n$ called the abstract $d$-dimensional rigidity matroids and conjectured that ${\mathcal R}_d(K_n)$ is the unique maximal element in this family. The conjecture turned out to be true for $d=1,2$ and false for $d\geq 4$, but it is still open when $d=3$. In the previous paper, the authors verified the case $d=3$ of a related conjecture of Whiteley, which replaced ${\mathcal R}_d(K_n)$ by another abstract rigidity matroid called the generic ${\mathcal C}^{d-2}_{d-1}$-cofactor matroid. Whiteley has also conjectured that the generic ${\mathcal C}^{d-2}_{d-1}$-cofactor matroid on $K_n$ is equal to ${\mathcal R}_d(K_n)$, which would imply that Graver’s conjecture holds for $d=3$, but that is still open.

Nevertheless, the importance of the generic $C_2^1$-cofactor matroid is now well-established, and the purpose of this paper is to give a combinatorial characterization of dependence in this matroid.

A circuit in a matroid is defined to be a minimal dependent set. (The name comes from the fact that the acyclic subsets of the edges of a graph are a very standard example of the independent sets in a matroid.) If $\mathcal C$ is a family of circuits in a matroid, a proper $\mathcal C$-sequence is defined to be a sequence $C_1,C_2,\dots,C_k$ of circuits in $\mathcal C$ such that no $C_i$ is contained in the union of its predecessors. Their importance comes from a lemma that states that for any such sequence the rank of a subset $X$ is bounded above by $|X\cup\bigcup_{i=1}^kC_i|-k$.

It turns out that copies of $K_5$ are circuits in any abstract 3-rigidity matroid, and, in particular, in the generic $C_2^1$-cofactor matroid of $K_n$. One of the main results of the paper is that the rank of a subset of $K_n$ in this matroid is actually equal to the bound above for some proper sequence of copies of $K_5$. (In particular this is true in the special case where the subset is itself a $K_5$: then we can take the sequence to consist just of that $K_5$ and we obtain the result that the rank is at most $\binom{5}{2}-1$, which agrees with the assertion that the copy of $K_5$ is a circuit.)

We thus have a combinatorial characterization of rank, and hence of independence. Note that to prove that a set has rank at least $r$ using this characterization, we have to show that there is no proper $K_5$-sequence that witnesses a bound lower than $r$. Since it is simple to check whether a given sequence witnesses such a bound, the characterization given demonstrates that the problem of determining whether a set is independent in the $C_2^1$-cofactor matroid of $K_n$ belongs to the complexity class co-NP. It turns out that the Schwarz-Zippel lemma can be used to prove that it is also in NP, so, like the graph homomorphism problem, the discrete logarithm problem (suitably formulated), and the unknot-recognition problem, it belongs to the interesting class NP$\cap$co-NP. Whether or not there is a polynomial-time algorithm remains an intriguing open problem.

The second author talks about the results in this video, which is the third in a series (the previous two videos of which are embedded in the editorial introduction to the previous article).