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

Abstract

A graph $G=(V,E)$ is $d$-sparse if each subset $X\subseteq V$ with $|X|\ge d$ induces at most $d|X|-\left(\genfrac{}{}{0ex}{}{d+1}{2}\right)$ edges in $G$. Maxwell showed in 1864 that a necessary condition for a generic bar-and-joint framework with at least $d+1$ vertices to be rigid in ${\mathbb{R}}^d$ is that $G$ should have a $d$-sparse subgraph with $d|X|-\left(\genfrac{}{}{0ex}{}{d+1}{2}\right)$ edges. This necessary condition is also sufficient when $d=1,2$ but not when $d\ge 3$. Cheng and Sitharam strengthened Maxwell's condition by showing that every maximal $d$-sparse subgraph of $G$ should have $d|X|-\left(\genfrac{}{}{0ex}{}{d+1}{2}\right)$ edges when $d=3$. We extend their result to all $d\le 11$.

There was an error in the proof of Theorem 3.3(b) in version 1 of this paper. A weaker statement was proved in version 2 and then used to derive the main result Theorem 4.1 when $d\le 5$. The proof technique was subsequently refined in collaboration with Hakan Guler to extend this result to all $d\le 11$ in Theorem 3.3 of version 3

References in corpus (1)

• Maxwell-independence: a new rank estimate for 3D rigidity matroids