Abstract 3-Rigidity and Bivariate -Splines II: Combinatorial Characterization

- School of Mathematical Sciences, Queen Mary University of London
- More about Bill Jackson

- Department of Mathematical Informatics, University of Tokyo
- More about Shin-ichi Tanigawa

*Discrete Analysis*, May. https://doi.org/10.19086/da.34692.

### Editorial introduction

Abstract 3-Rigidity and Bivariate -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 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 -dimensional rigidity matroid* of the graph. The generic -dimensional rigidity matroid of a graph is denoted by .

The matroid is particularly important, since a full description of this matroid will include descriptions of for all graphs on 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 called the *abstract -dimensional rigidity matroids* and conjectured that is the unique maximal element in this family. The conjecture turned out to be true for and false for , but it is still open when . In the previous paper, the authors verified the case of a related conjecture of Whiteley, which replaced by another abstract rigidity matroid called the generic -cofactor matroid. Whiteley has also conjectured that the generic -cofactor matroid on is equal to , which would imply that Graver’s conjecture holds for , but that is still open.

Nevertheless, the importance of the generic -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 is a family of circuits in a matroid, a *proper -sequence* is defined to be a sequence of circuits in such that no 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 is bounded above by .

It turns out that copies of are circuits in any abstract 3-rigidity matroid, and, in particular, in the generic -cofactor matroid of . One of the main results of the paper is that the rank of a subset of in this matroid is actually equal to the bound above for some proper sequence of copies of . (In particular this is true in the special case where the subset is itself a : then we can take the sequence to consist just of that and we obtain the result that the rank is at most , which agrees with the assertion that the copy of 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 using this characterization, we have to show that there is *no* proper -sequence that witnesses a bound lower than . 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 -cofactor matroid of 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 NPco-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).