Abstract 3-Rigidity and Bivariate C12-Splines II: Combinatorial Characterization
- School of Mathematical Sciences
- Queen Mary University of London
- More about Bill Jackson
Abstract 3-Rigidity and Bivariate C12-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 Rd 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 Rd(G).
The matroid Rd(Kn) is particularly important, since a full description of this matroid will include descriptions of Rd(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 Kn called the abstract d-dimensional rigidity matroids and conjectured that Rd(Kn) is the unique maximal element in this family. The conjecture turned out to be true for d=1,2 and false for d≥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 Rd(Kn) by another abstract rigidity matroid called the generic Cd−2d−1-cofactor matroid. Whiteley has also conjectured that the generic Cd−2d−1-cofactor matroid on Kn is equal to Rd(Kn), which would imply that Graver’s conjecture holds for d=3, but that is still open.
Nevertheless, the importance of the generic C12-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 C is a family of circuits in a matroid, a proper C-sequence is defined to be a sequence C1,C2,…,Ck of circuits in C such that no Ci 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∪⋃ki=1Ci|−k.
It turns out that copies of K5 are circuits in any abstract 3-rigidity matroid, and, in particular, in the generic C12-cofactor matroid of Kn. One of the main results of the paper is that the rank of a subset of Kn in this matroid is actually equal to the bound above for some proper sequence of copies of K5. (In particular this is true in the special case where the subset is itself a K5: then we can take the sequence to consist just of that K5 and we obtain the result that the rank is at most (52)−1, which agrees with the assertion that the copy of K5 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 K5-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 C12-cofactor matroid of Kn 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∩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).