6 Frameworks and infinitesimal rigidity
This section defines the rigidity of a graph placed in Euclidean space, and proves the facts about it that Laman’s theorem (section 9) uses. We follow the presentation in Jordán’s survey [ Jor16 ] (§1.2). A framework places each vertex of a graph at a point of \({\mathbb {R}}^{d}\). Its infinitesimal motions assign a velocity to each vertex so that no edge changes length to first order. They form the kernel of a linear map, the rigidity map. The translations and rotations of \({\mathbb {R}}^{d}\) give the trivial infinitesimal motions, and a framework is infinitesimally rigid when it has no others. A graph is generically rigid when some framework of it is infinitesimally rigid.
After the definitions we bound the rank of the rigidity map by the number of edges. We show that rigidity is preserved by adding edges and by isomorphisms, and that infinitesimal rigidity survives a small change of the framework. We then prove that a graph on \(n\) vertices that is generically rigid in \({\mathbb {R}}^{d}\) has at least \(dn - d(d+1)/2\) edges. The section ends with the complete graph \(K_2\), which is generically rigid in every dimension and is the base case of the induction in section 9.
Throughout, \(G\) is a graph on a set \(V\), which is finite where a statement says so, and \(d \in {\mathbb {N}}\). We equip \({\mathbb {R}}^{d}\) with its standard inner product \(\langle \cdot , \cdot \rangle \). As in section 5, we write \(uv\) for the edge with endpoints \(u\) and \(v\).
6.1 Definitions
A framework on \(V\) in \({\mathbb {R}}^{d}\) is a map \(p : V \to {\mathbb {R}}^{d}\), which places each vertex \(v\) at the point \(p_v\). The frameworks on \(V\) in \({\mathbb {R}}^{d}\) form the real vector space \(({\mathbb {R}}^{d})^{V}\).
Jordán’s framework is the pair \((G, p)\) of a graph and such a map. Here a framework is the map alone, and the graph enters each notion below as a separate argument. We also call a framework a placement of \(V\).
Let \(V\) be finite. Then \(\dim _{{\mathbb {R}}} ({\mathbb {R}}^{d})^{V} = d\, |V|\).
The space \(({\mathbb {R}}^{d})^{V}\) is a product of \(|V|\) copies of \({\mathbb {R}}^{d}\), each of dimension \(d\).
Let \(p\) be a framework, and let each vertex \(v\) move with velocity \(p'_v\), along the line \(t \mapsto p_v + t\, p'_v\). The squared length of an edge \(uv\) then has derivative \(2 \langle p_u - p_v,\, p'_u - p'_v \rangle \) at \(t = 0\). The rigidity map records these derivatives, without the factor \(2\).
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). The rigidity map of \(G\) at \(p\) is the linear map \(R(G, p) : ({\mathbb {R}}^{d})^{V} \to {\mathbb {R}}^{E(G)}\) given by
for \(p' \in ({\mathbb {R}}^{d})^{V}\) and each edge \(uv\) of \(G\).
The right-hand side is unchanged when \(u\) and \(v\) are exchanged, since both of its factors change sign, so it defines a value at the edge \(uv\). It is linear in \(p'\). In the standard bases, the matrix of \(R(G, p)\) is Jordán’s rigidity matrix (p. 36). The kernel of \(R(G, p)\) is the space of infinitesimal motions of \(G\) at \(p\).
We record the defining formula as a lemma, which later proofs cite when they evaluate the rigidity map at an edge.
Let \(uv\) be an edge of \(G\), and let \(p\) and \(p'\) be frameworks on \(V\) in \({\mathbb {R}}^{d}\). Then
Immediate from the definition.
Each translation and each infinitesimal rotation of \({\mathbb {R}}^{d}\) gives an infinitesimal motion of \(G\) at \(p\), whatever the graph \(G\) is. Together they give the motions \(p'_v = A p_v + b\), for a skew-symmetric \(d \times d\) matrix \(A\) and a vector \(b \in {\mathbb {R}}^{d}\). These are the trivial infinitesimal motions (Jordán, p. 36; section 8). The pairs \((A, b)\) form a space of dimension \(d(d+1)/2\), so the trivial motions form a space of dimension at most \(d(d+1)/2\). Equality holds when the points \(p_v\) affinely span \({\mathbb {R}}^{d}\) (lemma 8.12). A framework is infinitesimally rigid when all of its infinitesimal motions are trivial. We state this as a bound on the dimension of the kernel, the form that rank–nullity arguments use.
Let \(V\) be finite, and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). We say that \(p\) is infinitesimally rigid for \(G\) if
When the points \(p_v\) affinely span \({\mathbb {R}}^{d}\), the kernel contains the trivial motions, a space of dimension \(d(d+1)/2\), so the definition says that every infinitesimal motion is trivial. In general, by rank–nullity and lemma 6.2, it says that \(R(G, p)\) has rank at least \(d|V| - d(d+1)/2\). Jordán (pp. 36–37) asks instead that the rank attain the bound \(S(|V|, d)\) of his Lemma 1.2.1. This bound is \(d|V| - d(d+1)/2\) when \(|V| \ge d + 2\) and \(|V|(|V| - 1)/2\) when \(|V| \le d + 1\); the two expressions agree at \(|V| = d\) and at \(|V| = d + 1\). The rank never exceeds \(S(|V|, d)\), so the two definitions agree when \(|V| \ge d\). They also agree when \(|V| \le 1\), where both hold for every \(p\). In particular they agree for every \(V\) in the plane, the case of Laman’s theorem. When \(2 \le |V| \le d - 1\), which needs \(d \ge 3\), the definition above is weaker. For instance, two vertices with no edge between them, placed anywhere in \({\mathbb {R}}^{3}\), satisfy it, since the kernel has dimension \(6\); yet the two vertices can move apart.
Let \(V\) be finite. The graph \(G\) is generically rigid in dimension \(d\) if some framework on \(V\) in \({\mathbb {R}}^{d}\) is infinitesimally rigid for \(G\).
Defining generic rigidity through a single framework avoids generic frameworks, those whose coordinates are algebraically independent over \({\mathbb {Q}}\). Jordán (p. 38) calls \(G\) rigid in \({\mathbb {R}}^{d}\) when its generic frameworks are rigid: every continuous motion of the vertices that keeps each edge length fixed comes from an isometry of \({\mathbb {R}}^{d}\). For \(|V| \ge d\), where infinitesimal rigidity has Jordán’s meaning (formalization note 6.6), the two notions agree, for two reasons. At a generic framework, rigidity and infinitesimal rigidity are equivalent, by a theorem of Asimow and Roth [ AR78 ] . And the rigidity map has its largest rank at a generic framework, since its entries are polynomials in the coordinates with integer coefficients (Jordán, pp. 38–39).
Let \(V\) be finite. The graph \(G\) is injectively generically rigid in dimension \(d\) if some injective framework on \(V\) in \({\mathbb {R}}^{d}\) is infinitesimally rigid for \(G\).
An injectively generically rigid graph is generically rigid. The induction that proves Laman’s theorem (theorem 9.2) keeps an injective framework at each step, and weakens to generic rigidity at the end. Its step for each Henneberg move places the new vertex using that the move’s vertices \(a\) and \(b\) lie at distinct points (section 7). In positive dimension the two notions agree, since an infinitesimally rigid framework can be moved slightly to an injective one (section 6.5).
6.2 Rank and kernel bounds
We compare the kernels of the rigidity maps of two graphs, one of which contains the edges of the other, and we bound the rank of the rigidity map by the number of edges. The first gives the monotonicity results below, and the second gives the edge-count bound.
Let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). Then
Let \(p' \in \ker R(G', p)\). At each edge of \(G\), the value of \(R(G, p)(p')\) equals the value of \(R(G', p)(p')\) at the same edge of \(G'\), which is zero.
Let \(V\) be finite, and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). Then the rank of \(R(G, p)\) is at most \(|E(G)|\).
The range of \(R(G, p)\) lies in \({\mathbb {R}}^{E(G)}\), which has dimension \(|E(G)|\).
6.3 Graph monotonicity
Adding edges to a graph preserves each form of rigidity, at the same framework.
Let \(V\) be finite, let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). If \(p\) is infinitesimally rigid for \(G\), then \(p\) is infinitesimally rigid for \(G'\).
The kernel of \(R(G', p)\) lies in that of \(R(G, p)\) (lemma 6.9), so its dimension is at most \(d(d+1)/2\).
Let \(V\) be finite, and let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\). If \(G\) is generically rigid in dimension \(d\), then so is \(G'\).
A framework that is infinitesimally rigid for \(G\) is infinitesimally rigid for \(G'\) (lemma 6.11).
Let \(V\) be finite, and let \(G'\) be a graph on \(V\) with \(E(G) \subseteq E(G')\). If \(G\) is injectively generically rigid in dimension \(d\), then so is \(G'\).
An injective framework that is infinitesimally rigid for \(G\) is infinitesimally rigid for \(G'\) (lemma 6.11), and it is still injective.
6.4 Transport along graph isomorphism
Rigidity is invariant under isomorphism, as sparsity is (lemma 3.11). The induction in section 9 uses this for graphs that are identified only up to isomorphism, such as a Laman graph on two vertices and \(K_2\).
Let \(V\) and \(W\) be finite, let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\) on \(W\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). If \(p\) is infinitesimally rigid for \(G\), then \(p \circ \varphi ^{-1}\) is infinitesimally rigid for \(H\).
Composition with \(\varphi \) is a linear isomorphism from \(({\mathbb {R}}^{d})^{W}\) to \(({\mathbb {R}}^{d})^{V}\), sending \(q'\) to \(q' \circ \varphi \). Let \(uv\) be an edge of \(G\), so that \(\varphi (u)\varphi (v)\) is an edge of \(H\). The value of \(R(H, p \circ \varphi ^{-1})(q')\) at \(\varphi (u)\varphi (v)\) is \(\langle p_u - p_v,\, q'_{\varphi (u)} - q'_{\varphi (v)} \rangle \) (lemma 6.4), which is the value of \(R(G, p)(q' \circ \varphi )\) at \(uv\). Since \(\varphi \) maps the edges of \(G\) onto those of \(H\), the vector \(q'\) is an infinitesimal motion of \(H\) at \(p \circ \varphi ^{-1}\) if and only if \(q' \circ \varphi \) is an infinitesimal motion of \(G\) at \(p\). So composition with \(\varphi \) maps the one kernel isomorphically onto the other, and the two kernels have the same dimension.
Let \(V\) and \(W\) be finite, and let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\) on \(W\). If \(G\) is generically rigid in dimension \(d\), then so is \(H\).
If \(p\) is infinitesimally rigid for \(G\), then \(p \circ \varphi ^{-1}\) is infinitesimally rigid for \(H\) (lemma 6.14).
Let \(V\) and \(W\) be finite, and let \(\varphi \) be an isomorphism from \(G\) to a graph \(H\) on \(W\). If \(G\) is injectively generically rigid in dimension \(d\), then so is \(H\).
If \(p\) is injective and infinitesimally rigid for \(G\), then \(p \circ \varphi ^{-1}\) is infinitesimally rigid for \(H\) (lemma 6.14). It is injective, since \(\varphi ^{-1}\) is a bijection.
6.5 Openness of infinitesimal rigidity
Infinitesimal rigidity is an open condition on the framework: every framework close enough to an infinitesimally rigid one is again infinitesimally rigid. So an infinitesimally rigid framework can be moved slightly, while staying infinitesimally rigid, to satisfy a further condition that holds on a dense open set of frameworks. The Type II step of the Henneberg induction (theorem 7.5) moves a point in this way, off the line through two others.
Let \(V\) be finite, and let \(p_0\) be a framework on \(V\) in \({\mathbb {R}}^{d}\) that is infinitesimally rigid for \(G\). Then every framework in some neighbourhood of \(p_0\) in \(({\mathbb {R}}^{d})^{V}\) is infinitesimally rigid for \(G\).
Let \(r\) be the rank of \(R(G, p_0)\), and choose \(\xi _1, \dots , \xi _r \in ({\mathbb {R}}^{d})^{V}\) whose images under \(R(G, p_0)\) form a basis of its range. The entry of \(R(G, p)(\xi _i)\) at an edge \(uv\) is the inner product of \(p_u - p_v\) with \((\xi _i)_u - (\xi _i)_v\) (lemma 6.4), so \(R(G, p)(\xi _i)\) depends continuously on \(p\). Linear independence of \(r\) vectors in the finite-dimensional space \({\mathbb {R}}^{E(G)}\) is an open condition. So for every \(p\) in some neighbourhood of \(p_0\) the vectors \(R(G, p)(\xi _1), \dots , R(G, p)(\xi _r)\) are linearly independent, and \(R(G, p)\) has rank at least \(r\).
For such \(p\), rank–nullity in \(({\mathbb {R}}^{d})^{V}\) shows that the kernel of \(R(G, p)\) has dimension at most that of the kernel of \(R(G, p_0)\), which is at most \(d(d+1)/2\).
6.6 The edge-count bound
Rank–nullity gives a lower bound on the number of edges of a generically rigid graph. In the plane it says that a graph on \(V\) that is generically rigid has at least \(2|V| - 3\) edges, as many as a Laman graph on \(V\) (lemma 9.1).
Let \(V\) be finite, and let \(G\) be generically rigid in dimension \(d\). Then
Let \(p\) be a framework that is infinitesimally rigid for \(G\). By rank–nullity, \(\dim ({\mathbb {R}}^{d})^{V}\) is the rank of \(R(G, p)\) plus the dimension of its kernel. Here \(\dim ({\mathbb {R}}^{d})^{V} = d\, |V|\) (lemma 6.2), the rank is at most \(|E(G)|\) (lemma 6.10), and the kernel has dimension at most \(d(d+1)/2\), since \(p\) is infinitesimally rigid. Together these give the bound.
The bound is stated in additive form because the formal statement counts in the natural numbers, in which \(d\, |V| - d(d+1)/2\) would be truncated at \(0\).
6.7 Worked example: \(K_2\) is generically rigid in every dimension
The complete graph \(K_2\) on two vertices is the base case of the induction in section 9, which needs it in the injective form.
Let \(d \ge 1\). Then the complete graph \(K_2\) on two vertices is injectively generically rigid in dimension \(d\).
Let \(u\) and \(v\) be the two vertices, and let \(e\) be the first standard basis vector of \({\mathbb {R}}^{d}\). The framework \(p\) with \(p_u = 0\) and \(p_v = e\) is injective. The velocities \(p'_u = e\) and \(p'_v = 0\) give \(R(K_2, p)(p')(uv) = \langle 0 - e,\, e - 0 \rangle = -1\) (lemma 6.4), so \(R(K_2, p)\) has rank at least \(1\). The space of frameworks has dimension \(2d\) (lemma 6.2), so by rank–nullity the kernel has dimension at most \(2d - 1\). Finally \(2d - 1 \le d(d+1)/2\), since the difference is \((d - 1)(d - 2)/2 \ge 0\).
Let \(d \in {\mathbb {N}}\). Then the complete graph \(K_2\) on two vertices is generically rigid in dimension \(d\).
For \(d \ge 1\) this follows from theorem 6.20. For \(d = 0\) the space of frameworks is \(\{ 0\} \), so the kernel of the rigidity map has dimension \(0 = d(d+1)/2\).