26 The molecule rank formula (KT Corollary 5.7)
Let \(G = (V, E)\) be a graph of minimum degree at least two. In this chapter we prove KT Corollary 5.7, the rank formula
where \(r = r_3\) is the generic rank in \({\mathbb {R}}^3\) (definition 24.7) and \(G^2\) is the square of \(G\) (definition 25.1). The deficiency \(\operatorname {def}(\tilde G)\) is that of definition 20.3 at \(D = 6\), with \(\tilde G = 5 \cdot G\). Jackson and Jordán conjectured the formula and proved the inequality \(\le \) [ JJ08a , Conjecture 2.2 and Theorem 4.1 ] . Their Conjecture 2.1 is the bar-joint form of the molecular conjecture of Tay and Whiteley [ TW84 ] , and they proved that the formula is equivalent to it (their Theorem 4.3). Katoh and Tanigawa deduce the formula from their Theorem 5.6, through Whiteley’s equivalence between molecular and bar-joint realizations and Jackson and Jordán’s Theorem 4.3 (KT p. 671).
We derive both inequalities from KT Theorem 5.6, through the equalities between dimensions of motion spaces that section 25 proves. The opening of that chapter outlines the argument and compares it with Jackson and Jordán’s. Section 26.1 shows that the rank of a graph at any placement is at most its generic rank. Section 26.2 passes from the simple graph \(G\) to a multigraph, on which the formalization states the deficiency and KT Theorem 5.6. Section 26.3 proves the two inequalities and the formula, and derives from it when the square of a graph is generically rigid.
26.1 The generic rank bounds the rank at every placement
At a placement that is generic for row independence, the rank of the rigidity map of a graph equals its generic rank (lemma 24.9). The lower bound compares the two at the centres of a molecular realization, which need not be generic.
Let \(H\) be a graph on a finite set \(V\), and let \(p\) be a placement of \(V\) in \({\mathbb {R}}^d\). Then
where \(r_e\) is the rigidity row of \(K_V\) at \(p\) indexed by \(e\) (definition 9.4). Equivalently, \(\operatorname {rank} R(H, p) \le r_d(H)\).
The linear rigidity matroid \(\mathcal{L}_p(V)\) is represented by the extended rigidity rows \(\tilde r_e\) at \(p\) (definition 10.16), and \(\tilde r_e = r_e\) for every edge \(e\) of \(K_V\). In a represented matroid, the vectors of a set span a space whose dimension is the rank of the set (lemma 16.7). So the span has dimension equal to the rank of \(E(H)\) in \(\mathcal{L}_p(V)\). A set that is independent in \(\mathcal{L}_p(V)\) is row-independent at \(p\) (lemma 10.17). It is therefore independent in \(\mathcal{R}_d(V)\) (lemma 24.4). Hence the rank of \(E(H)\) in \(\mathcal{L}_p(V)\) is at most its rank \(r_d(H)\) in \(\mathcal{R}_d(V)\).
The rank of \(R(H, p)\) is the dimension of the same span. Indeed, \(R(H, p)\) has the same rank as its transpose, whose image is spanned by the rigidity rows of \(H\) at \(p\) (lemma 9.5). For an edge \(uv\) of \(H\), the row of \(H\) at \(uv\) is \(x \mapsto \langle p_u - p_v,\, x_u - x_v \rangle \) (lemma 6.4), which is also the row \(r_{uv}\) of \(K_V\).
The first pin states the bound for the span, and the second the bound for \(\operatorname {rank} R(H, p)\), which the proof of lemma 26.5 uses.
26.2 Simple graphs as multigraphs
Katoh and Tanigawa state their Theorem 5.6 for multigraphs, and the deficiency is defined for a multigraph (definition 20.3). We regard the simple graph \(G\) as a multigraph. In the formalization this step is the following lemma.
Let \(G\) be a simple graph on a finite set \(V\). Then there is a simple multigraph \(G'\) with vertex set \(V\), in which two distinct vertices are joined by an edge if and only if they are adjacent in \(G\).
Take as labels the \(|V|(|V| + 1)/2\) unordered pairs of elements of \(V\). For each edge \(uv\) of \(G\), let \(G'\) have one edge joining \(u\) and \(v\), labelled by the pair \(\{ u, v\} \). Distinct edges of \(G'\) have distinct labels, hence distinct pairs of ends, and no edge is a loop, as \(G\) has none. So \(G'\) is simple, and its edges join exactly the adjacent pairs of \(G\).
In the formalization, simple graphs and multigraphs are different objects. The square and the generic rank are defined for simple graphs, and the deficiency and the frameworks of section 25 for multigraphs, whose edges are drawn from a fixed set of labels (formalization note 21.11). The first pin is \(G'\), with the unordered pairs of \(V\) as its labels, and the next three are its simplicity, its vertex set and its edges. The pinned forms of the three results below state the deficiency of \(G'\), and apply the results of section 25 to \(G'\).
A partition of \(V\) separates as many edges of \(G'\) as of \(G\), since the edges of \(G'\) join exactly the adjacent pairs of \(G\). So \(G'\) and \(G\) have the same deficiency. It is the deficiency \(\operatorname {def}(G)\) of Jackson and Jordán [ JJ08a , § 2 ] , the largest value of \(6(|P| - 1) - 5\, e_G(P)\) over the partitions \(P\) of \(V\), where \(e_G(P)\) is the number of edges of \(G\) that join different parts of \(P\). We write \(\operatorname {def}(\tilde G)\) for it, as Katoh and Tanigawa do.
26.3 The two inequalities and the formula
Both inequalities pass from molecular frameworks on \(G\) to bar-joint frameworks on \(G^2\) by the square-graph dictionary (theorem 25.22). The dictionary applies at placements in general position up to order four, and it needs every vertex of \(G\) to have degree at least two.
Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\). Then \(3|V| - 6 - \operatorname {def}(\tilde G) \le r(G^2)\).
Regard \(G\) as a multigraph, as in lemma 26.3. By theorem 25.20 there is a placement \(c \colon V \to {\mathbb {R}}^3\) in general position up to order four such that the molecular framework on \((G, c)\) has \(\dim Z_{\mathrm{mol}}(G, c) = 6 + \operatorname {def}(\tilde G)\). By the square-graph dictionary (theorem 25.22),
The generic rank \(r(G^2)\) is at least this rank (lemma 26.1).
Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\). Then \(r(G^2) \le 3|V| - 6 - \operatorname {def}(\tilde G)\).
Regard \(G\) as a multigraph, as in lemma 26.3. Let \(p \colon V \to {\mathbb {R}}^3\) be a placement that is generic for row independence and in general position up to order four (lemma 25.17). As \(p\) is generic, the rank of \(R(G^2, p)\) is \(r(G^2)\) (lemma 24.9). So the square-graph dictionary (theorem 25.22) gives
As \(p\) is in general position, the centres \(p(v)\) are distinct, so the hinges of the molecular framework on \((G, p)\) are nondegenerate. Hence \(\dim Z_{\mathrm{mol}}(G, p) \ge 6 + \operatorname {def}(\tilde G)\) (lemma 20.15), and the bound follows.
The pinned form of the dictionary takes the molecular framework with an endpoint selector that assigns each edge its two ends (formalization note 23.6). The pinned lemma builds one. It assigns each edge of the multigraph of lemma 26.3 its two ends, and every other label one fixed pair of adjacent vertices of \(G\). So every label has two distinct ends, and as \(p\) is injective, a nonzero hinge.
Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\). Then
where \(r\) is the rank function of the generic rigidity matroid \(\mathcal{R}_3(V)\) (definition 24.7), and \(\operatorname {def}(\tilde G)\) is the deficiency of definition 20.3 at \(D = 6\), with \(\tilde G = 5 \cdot G\).
Combine lemma 26.5 and lemma 26.6.
The formula decides when the square of a graph is rigid. As \(\operatorname {def}(\tilde G) \ge 0\), it gives \(r(G^2) \le 3|V| - 6\), with equality if and only if \(\operatorname {def}(\tilde G) = 0\), that is, if and only if \(5 \cdot G\) contains six edge-disjoint spanning trees (lemma 20.14).
A placement \(p\) is infinitesimally rigid for \(G^2\) if and only if \(\operatorname {rank} R(G^2, p) \ge 3|V| - 6\) (definition 6.5). This rank is at most \(r(G^2)\) (lemma 26.1). At a placement that is generic for row independence it equals \(r(G^2)\) (lemma 24.9). So \(G^2\) is generically rigid in \({\mathbb {R}}^3\) (definition 6.7) if and only if \(5 \cdot G\) contains six edge-disjoint spanning trees. This is Jackson and Jordán’s Conjecture 2.1 [ JJ08a ] . Katoh and Tanigawa note it as a corollary of their work (KT §7). When \(5 \cdot G\) contains six edge-disjoint spanning trees, every placement that is generic for row independence is infinitesimally rigid for \(G^2\) (corollary 28.3).