17 Body-hinge Tay–Whiteley theorem
A body-hinge framework in \({\mathbb {R}}^d\) consists of rigid bodies joined by hinges. A hinge is a \((d-2)\)-dimensional affine subspace shared by two bodies: a pin joint in the plane, a line in \(3\)-space, a plane in \(4\)-space [ Whi88 , § 3.3 ] . The two bodies can rotate relative to each other only about the hinge. This chapter proves the theorem of Tay [ Tay89 ] and Whiteley [ Whi88 ] on these frameworks. It characterizes the graphs of the independent body-hinge frameworks, and those of the independent and infinitesimally rigid ones. As with Tay’s theorem in section 16, we prove it in the existence form.
As in section 16, let \(D = \binom {d+1}{2}\). The relative screws of two bodies form a space of dimension \(D\), and a hinge between them leaves a space of dimension one, the rotations about the hinge. So the hinge acts as \(D - 1\) bars, all meeting the hinge, whose Plücker vectors are linearly independent (Whiteley [ Whi88 , proof of Theorem 10 ] ). Replacing each hinge by such a bundle of bars turns a body-hinge framework on a multigraph \(G\) into a body-bar framework on the multigraph \((D-1)\cdot G\), in which each edge of \(G\) is repeated \(D - 1\) times. We apply Tay’s theorem (theorem 16.27) to \((D-1)\cdot G\). The result, theorem 17.5, is that \(G\) has an independent body-hinge framework if and only if the edges of \((D-1)\cdot G\) form a union of \(D\) disjoint forests, and an independent and infinitesimally rigid one if and only if \((D-1)\cdot G\) is \((D, D)\)-tight.
17.1 Body-hinge frameworks and the hinge-to-bar reduction
We define the multigraph \((D-1)\cdot G\) and body-hinge frameworks, and we apply Tay’s theorem to \((D-1)\cdot G\).
Let \(G\) be a multigraph and let \(m\) be a natural number. The multigraph \(m \cdot G\) has the vertices of \(G\), and for each edge \(e\) of \(G\) it has \(m\) edges \((e, 1), \dots , (e, m)\), each with the ends of \(e\).
So \(|E(m \cdot G)| = m\, |E(G)|\) (Graph.edgeMultiply_edgeSet_ncard). For \(m \ge 1\), a set of edges of \(G\) meets the same vertices as the set of their copies in \(m \cdot G\) (Graph.spanningVerts_edgeMultiply). Katoh and Tanigawa write \(\tilde G\) for \((D-1)\cdot G\) [ KT11 , § 1 ] , and so do the later chapters.
Let \(D = \binom {d+1}{2}\), and let \(G\) be a multigraph. A body-hinge framework in \({\mathbb {R}}^d\) on \(G\) assigns to each edge \(e\) of \(G\) a \((d-2)\)-dimensional affine subspace of \({\mathbb {R}}^d\), the hinge of \(e\), and to the \(D - 1\) copies of \(e\) in \((D-1)\cdot G\) a basis of the space spanned by the Plücker vectors of the lines that meet the hinge. Its rigidity map is that of the body-bar framework on \((D-1)\cdot G\) with these vectors (definition 16.22). It is independent, or infinitesimally rigid, if this body-bar framework is.
The formalization records a body-hinge framework on \(G\) by its vectors alone. It is a body-bar framework on \((D-1)\cdot G\), with no hinge and no condition on the \(D - 1\) vectors of an edge. So lemma 17.4 and theorem 17.5 are proved for these bundles of bars, and the frameworks they provide need not come from hinges. For multigraphs, the formalization has the theorem in this form. The rigidity statement for frameworks with hinges (definition 19.3), at every generic choice of the hinges, is corollary 28.44, and it is for multigraphs, with parallel edges and loops allowed. It also asks that every body be a vertex of \(G\) and that the field be infinite, and nothing of the edge labels, as the formalization note after it describes.
Let \(D = \binom {d+1}{2}\), and let \(G\) be a multigraph. Then there is an independent body-hinge framework in \({\mathbb {R}}^d\) on \(G\) if and only if \((D-1)\cdot G\) is \((D, D)\)-sparse. There is a body-hinge framework in \({\mathbb {R}}^d\) on \(G\) that is independent and infinitesimally rigid if and only if \((D-1)\cdot G\) is \((D, D)\)-tight.
By definition 17.2, a body-hinge framework on \(G\) is independent, or infinitesimally rigid, exactly when the body-bar framework on \((D-1)\cdot G\) with the same vectors is. In the formalization every body-bar framework on \((D-1)\cdot G\) arises in this way, as the formalization note after definition 17.2 explains (Graph.BodyHingeFramework.exists_toBodyBar_iff). So the two statements are those of theorem 16.27 for the multigraph \((D-1)\cdot G\).
Since \(|E((D-1)\cdot G)| = (D-1)|E(G)|\), the multigraph \((D-1)\cdot G\) is \((D, D)\)-tight if and only if \((D-1)|E(G)| = D|V(G)| - D\) and \((D-1)|E'| \le D|V(E')| - D\) for every non-empty set \(E'\) of edges of \(G\). These inequalities suffice, because a set of edges of \((D-1)\cdot G\) meets the same vertices as the set of all copies of the edges of \(G\) that it uses, and is no larger.
17.2 The Tay–Whiteley theorem
Tay [ Tay89 , § 7 ] and Whiteley [ Whi88 , Theorem 10 ] characterized, independently, the graphs of the infinitesimally rigid body-hinge frameworks. Whiteley’s introduction also states the characterization of the graphs of the independent ones.
Let \(D = \binom {d+1}{2}\), and let \(G\) be a multigraph. Then there is an independent body-hinge framework in \({\mathbb {R}}^d\) on \(G\) if and only if \(E((D-1)\cdot G)\) is the union of \(D\) pairwise disjoint forests. There is a body-hinge framework in \({\mathbb {R}}^d\) on \(G\) that is independent and infinitesimally rigid if and only if \((D-1)\cdot G\) is \((D, D)\)-tight.
By lemma 17.4, there is an independent body-hinge framework on \(G\) if and only if \((D-1)\cdot G\) is \((D, D)\)-sparse. By theorem 16.18, this holds if and only if \(E((D-1)\cdot G)\) is the union of \(D\) pairwise disjoint forests. The second statement is that of lemma 17.4.
If \(G\) is connected, then so is \((D-1)\cdot G\). By corollary 16.19, the second condition then makes \(E((D-1)\cdot G)\) the union of \(D\) disjoint spanning trees. Katoh and Tanigawa state the theorem for infinitesimal rigidity alone (KT Proposition 1.1): \(G\) has an infinitesimally rigid body-hinge framework in \({\mathbb {R}}^d\) if and only if \(\tilde G\) contains \(D\) edge-disjoint spanning trees. For frameworks with hinges at a generic choice of points, this form is corollary 28.44, which also asks that the field be infinite. The formalization also has the theorem above, for multigraphs, proved for bundles of bars as the note after the definition of body-hinge frameworks explains.
Katoh and Tanigawa call a body-hinge framework a panel-hinge framework if, for each body, the hinges at that body lie in a common hyperplane [ KT11 , § 1 ] . Tay and Whiteley [ TW84 ] conjectured that a graph has an infinitesimally rigid body-hinge framework in \({\mathbb {R}}^d\) if and only if it has an infinitesimally rigid panel-hinge framework in \({\mathbb {R}}^d\) (KT Conjecture 1.2). This is the molecular conjecture. It does not follow from theorem 17.5, which places no condition on the hinges at a body. Katoh and Tanigawa proved it, and we prove its case of simple graphs in theorem 23.56, following them.