## 11 Multivariate Splines and Cofactor Matroids
### \(C^{1}_{2}\) Is the Maximal Abstract \(3\)-Rigidity Matroid  
There is a recent theorem, confirming an earlier conjecture, that places these matroids central to the exploration of abstract \(3\)-rigidity [25; 26], see also [21; 35; 153; 154]. For a matroid \(M\), let \(cl_{M}\) denote the closure operator of \(M\). **Definition 14** (Graver [153]). : _A matroid \(M\) on \(K_{n}\) is an abstract \(d\)-rigidity matroid if the following two properties hold:_  
1. _If_ \(E_{1},E_{2}\subseteq E(K_{n})\) _with_ \(|V(E_{1})\cap V(E_{2})|\leq d-1\)_, then_ \(cl_{M}(E_{1}\cup E_{2})\subseteq K_{m}\) _where_ \(m=|V(E_{1})\cup V(E_{2})|\)_;_
2. _If_ \(E_{1},E_{2}\subseteq E(K_{n})\) _with_ \(cl_{M}(E_{1})=K_{n_{1}}\) _where_ \(n_{1}=|V(E_{1})|\)_,_ \(cl_{M}(E_{2})=K_{n_{2}}\) _where_ \(n_{2}=|V(E_{2})|\)_, and_ \(|V(E_{1})\cap V(E_{2})|\geq d\)_, then_ \(cl_{M}(E_{1}\cup E_{2})=K_{m}\) _where_ \(m=|V(E_{1}\cup E_{2})|\)_._  
The generic \(d\)-dimensional rigidity matroid for \(K_{n},M_{d}(G)\), is an example of an abstract d-rigidity matroid. Nguyen [154] showed that an equivalent definition of an abstract \(d\)-rigidity matroid is that every copy of \(K_{d+2}\) is a circuit, no smaller circuits exist and the rank is \(d|V|-\binom{d+1}{2}\). **Theorem 27** ([25]). : _The generic \(C^{1}_{2}\)-cofactor matroid on \(K_{n}\) is the unique maximal abstract \(3\)-rigidity matroid on \(E(K_{n})\)._  
The equality \(|E|=3n-6\) for bases in the \(C^{1}_{2}\)-cofactor matroid immediately implies that the graph \(G\) contains a vertex of degree \(3,4\) or \(5\). The proof of the theorem uses a sequence of construction steps to add such vertices to smaller maximal independent sets (outlined as a conjecture in [37] and extended in [25]). The proof shows that this matroid is the unique maximal abstract rigidity matroid in the sense that if a set of edges is independent in any abstract \(3\)-rigidity matroid, then it is independent in the generic \(C^{1}_{2}\)-cofactor matroid on the complete graph \(K_{n}\). In particular, any independent set in anyframework on \(K_{n}\) in \(\mathbb{P}^{3}\) will be independent in the generic \(C^{1}_{2}\)-cofactor matroid on the complete graph \(K_{n}\). The recursive proof technique gives the following construction. **Corollary 9**. : _All bases in the maximal abstract \(3\)-rigidity matroid can be derived from a triangle by an inductive construction using the following steps:_  
1. \(0\)_-extensions (i.e., vertex addition) (Figure 66a);_
2. \(1\)_-extensions (i.e., edge splitting) (Figure 66b);_
3. \(X\)_-replacement (Figure 67a);_
4. _double V-replacement (Figure 67b)._  
In a broad sense, this is an extension of Laman's proof of the characterisation of generic rigidity in \(2\)-dimensions by induction based on the first two steps above, as \(|E|\leq 2|V|-3\) guarantees there are vertices of degree at most \(3\). It is not yet proven whether the generic rigidity matroid for \(d=3\) is also maximal. A key gap is the absence of a proof that \(X\)-replacement preserves generic rigidity when \(d=3\). It appears that, with that added step, the proof for double-V replacement will extend to generic rigidity. A key unsolved problem that remains is to find fast deterministic algorithms for the rigidity of generic frameworks with maximal rank for generic rigidity or for the \(C^{1}_{2}\)-cofactor matroid. There are pure conditions for \(C^{1}_{2}\)-splines in the plane which capture the projective geometric conditions for dependencies for generically independent graphs [24]. For example, for the graph of an octahedron, the pure condition is that one of the triangles is collinear or that three edges joining opposite vertices are concurrent [24].