The d-dimensional rigidity matroid of sparse graphs

Let R d ( 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 R d ( 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 ) ⩽ 1 2 [ ( d + 2 ) | X | - ( 2 d + 2 ) ] for all X ⊆ V with | X | ⩾ 2 then E is independent in R d ( 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 R d ( G ) . We use the case d = 4 to show that, if G is 10-connected, then G can be made rigid in R 3 by pinning down approximately three quarters of its vertices.