The \(d\)-dimensional rigidity matroid of sparse graphs (Q2565690)

For a graph \(G\) with vertices of degree \(d+1\) or \(d+2\) the rank funcion of the \(d\)-dimensional generic rigidity matroid \(\mathcal{R}_d (G)\) is determined via a min-max formula. For even \(d\) it is shown that the edge set \(E(G)\) is independent in \(\mathcal{R}_d (G)\) if every subset \(X\) of the vertex set containing at least two vertices induces a subgraph containing at most \(1/2[(d+2)| X| -(2d+2)]\) edges. The authors conjecture that this holds also for odd \(d\) and provide a proof for \(d=3\). Moreover, the authors use the independence result for even \(d\), to show that if the connectivity of \(G\) is large in comparison to \(d\) then \(E(G)\) has large rank in \(\mathcal{R}_d (G)\). The case \(d=4\) is used to show that a 10-connected graph can be made rigid in 3-space by pinning approximately three quarters of its vertices. The Lovász and Yemini conjecture that 12-connectivity might be sufficient to insure the rigidity of a graph in 3-space is still open.