The d-dimensional rigidity matroid of sparse graphs

AbstractLet Rd(G) be the d-dimensional rigidity matroid for a graph G=(V,E). For X⊆V let i(X) be the number of edges in the subgraph of G induced by X. We derive a min-max formula which determines the rank function in Rd(G) when G has maximum degree at most d+2 and minimum degree at most d+1. We also show that if d is even and i(X)⩽12[(d+2)|X|-(2d+2)] for all X⊆V with |X|⩾2 then E is independent in Rd(G). We conjecture that the latter result holds for all d⩾2 and prove this for the special case when d=3. We use the independence result for even d to show that if the connectivity of G is sufficiently large in comparison to d then E has large rank in Rd(G). We use the case d=4 to show that, if G is 10-connected, then G can be made rigid in R3 by pinning down approximately three quarters of its vertices