A necessary condition for generic rigidity of bar-and-joint frameworks in d-space

Abstract

A graph (Formula presented.) is (Formula presented.) -sparse if each subset (Formula presented.) with (Formula presented.) induces at most (Formula presented.) edges in (Formula presented.). Maxwell showed in 1864 that a necessary condition for a generic bar-and-joint framework with at least (Formula presented.) vertices to be rigid in (Formula presented.) is that (Formula presented.) should have a (Formula presented.) -sparse subgraph with (Formula presented.) edges. This necessary condition is also sufficient when (Formula presented.) but not when (Formula presented.). Cheng and Sitharam strengthened Maxwell's condition by showing that every maximal (Formula presented.) -sparse subgraph of (Formula presented.) should have (Formula presented.) edges when (Formula presented.). We extend their result to all (Formula presented.).