Abstract
We present necessary and sufficient conditions for the generic rigidity of body–bar frameworks on the three-dimensional fixed torus. These frameworks correspond to infinite periodic body–bar frame-works in with a fixed periodic lattice.
1. Introduction
The study of periodic structures from the perspective of rigidity theory has received considerable attention in recent years, owing in part to questions raised about the material properties of zeolites. Zeolites are a type of microporous mineral, the molecular structure of which is periodic in nature. Since the properties of zeolites are related to their structural properties, it has been a topic of interest to determine theoretically when such a material is rigid or flexible [1].
Towards this end, there has been a surge of interest in the study of periodic frameworks. A periodic framework is composed of rigid bars linked together periodically to form an infinite repetitive bar–joint framework, that is, rigid bars connected by flexible joints. This can be described by an infinite graph , together with a group, say Γ, which describes the periodicity of the graph . Together with a periodic placement of the vertices of in , we have a periodic framework [2]. The periodicity of the framework determines the periodic lattice, which we may consider as either fixed or variable. The periodic lattice is generated by the d translations under which is invariant.
In [3], a combinatorial characteri- zation for the generic rigidity of two-dimensional periodic frameworks with a fixed periodic lattice was presented. That is, we found combinatorial conditions on a periodic orbit graph which are sufficient to guarantee the rigidity of almost all realizations of the graph as periodic frameworks. Subsequent work by Malestein & Theran [4] characterized two-dimensional periodic frameworks with a variable periodic lattice. Unfortunately, like the study of the rigidity of finite graphs, we lack combinatorial tools to predict the generic rigidity of periodic frameworks for d>2.
It is natural, then, that we turn our attention to periodic body–bar frameworks, which are formed of rigid bodies linked periodically together by bars (two bodies can be linked by multiple bars, hence body–bar frameworks are captured by multi-graphs, in contrast to bar–joint frameworks which are always described by simple graphs). In their finite incarnations, body–bar frameworks admit neat combinatorial characterizations for all d [5]. The question then becomes: do periodic body–bar frameworks also have a nice combinatorial characterization?
In [3], a complete characterization of periodic body–bar frameworks with a fixed lattice was conjectured by the author. In this paper, we prove the result for d=3 (with d=1,2 following from the previous bar–joint characterizations [3]). In particular, we show:
Theorem 1.1
〈H,m〉 is a periodic orbit graph corresponding to a generically minimally rigid body–bar periodic framework in if and only if
|E(H)|=6|V (H)|−3
for all non-empty subsets Y ⊂E(H) of edges
The sparsity condition described by condition 2 depends on the dimension of the gain space of a set of edges Y , which, roughly speaking, can be thought of as part of the connectivity information about the periodic framework. Alternatively, describes the way in which the set of edges Y ‘wrap’ around a torus (as a model of periodic space), and can thus be seen as information about the homotopy type of the edge set Y .
Unlike their finite counterparts, we offer no general proof for periodic body–bar frameworks in higher dimensions (d≥4). While we conjecture that the analogous statement is true (see conjecture 5.1), the present combinatorial methods do not seem to be easily extendible to higher dimensions. In [6], using entirely different methods, the conjectured statement is established as a special case of a far more general result about symmetric frameworks. It nevertheless remains an open question whether the inductive methods presented here can be extended to higher dimensions.
We mention some related work due to Borcea et al. [7]. In that paper, the authors find necessary and sufficient combinatorial conditions for rigidity on unlabelled quotient graphs of infinite periodic body–bar frameworks. The work in this paper is concerned with labelled quotient graphs of infinite periodic frameworks. Given a particular infinite periodic body–bar framework, this defines a unique (up to the size of a unit cell and translation) labelled quotient graph, which we will call a periodic orbit framework. The analysis of labelled quotient graphs is a harder problem than the analysis of unlabelled ones. The approach of Borcea et al. [7] will only tell us that a good labelling (‘lifting’) of the quotient graph exists, but cannot predict whether a particular labelling will be good. That said, the paper [7] considers d-dimensional frameworks, and does so with a variable periodic lattice. This is, strictly speaking, a harder problem to characterize than the fixed lattice considered here. To further differentiate the present work from [7], the methods used here are inductive methods, while the approach of Borcea et al. is non-inductive.
We conclude this brief introduction by mentioning some reasons why it may be valuable to consider periodic frameworks with a fixed periodic lattice. It may, at first glance, seem like an unnatural restriction or simplification of the problem of periodic frameworks (with a variable lattice). However, for frameworks with a variable periodic lattice which are flexible, the vertices which are ‘far away’ from the ‘centre’ (arbitrarily chosen) are moving arbitrarily quickly. Some materials scientists have suggested that the time scales of lattice movement are several orders of magnitude slower than molecular deformation within the lattice (M. Thorpe 2010, personal communication). Finally, we may also view the fixed lattice as a stepping stone or preview of a full characterization of frameworks with a variable lattice. In particular, it is possible to view characterizations of frameworks with a variable lattice as consisting of two parts: a component which ‘rigidifies’ the variability of the lattice, and a second component which is rigid within the resulting fixed lattice.
(a) Outline of paper
We provide an extensive background (§2) which outlines several types of frameworks, and their rigidity. In particular, we discuss finite bar–joint frameworks, bar–joint periodic orbit frameworks and their corresponding derived periodic (bar–joint) frameworks, finite body–bar frameworks, body–bar periodic orbit frameworks and their corresponding derived periodic (body–bar) frameworks. We also describe induced bar–joint frameworks from body–bar frameworks. Section 2e provides information about rigidity-preserving inductive constructions for three-dimensional bar–joint periodic orbit frameworks. In §3, we state and motivate our main result, and establish the necessity of the characterization. Section 4 is the main work of the paper, and details the proof of the sufficiency of the characterization. We conclude with some conjectures and ideas for further work.
2. Background
In this section, we outline the basic notions of finite and periodic bar–joint frameworks, and finite and periodic body–bar frameworks.
(a) Finite bar–joint frameworks
A bar–joint framework (G,p) is a finite simple graph G together with a position of the vertices of G in Euclidean space, , with p(v_{i})≠p(v_{j}) for all {v_{i},v_{j}}∈E(G). We write p(v_{i})=p_{i}, . An infinitesimal motion of (G,p) is a function (we write u(v_{i})=u_{i}) such that In other words, an infinitesimal motion instantaneously preserves the lengths of the bars of the framework. An infinitesimal motion of (G,p) is trivial if it corresponds to an infinitesimal rigid motion (e.g. a rotation or translation). If the only infinitesimal motions of (G,p) are trivial, we say that (G,p) is infinitesimally rigid, otherwise (G,p) is infinitesimally flexible.
It is clear that if the graph G is disconnected, then (G,p) is always infinitesimally flexible, hence we assume throughout that G is connected.
In this paper, we focus our attention on infinitesimal rigidity, which is sufficient to guarantee the continuous rigidity of a framework in , although the converse is false. The focus on infinitesimal rigidity is thus a typical way to attack the problem of continuous rigidity, which is computationally challenging. See any basic reference on rigidity theory for details [8–11].
The vector space of infinitesimal motions of a framework (G,p) is given by the kernel of the rigidity matrix, R(G,p). This is the |E|×d|V | matrix with d columns for each vertex, and one row corresponding to each edge e={v_{i},v_{j}}∈E(G), as follows: where the non-zero entries occur in the columns corresponding to vertices v_{i} and v_{j}, respectively. Note that there will always be a (^{d+1}_{2}) -dimensional space of trivial solutions of R(G,p), corresponding to infinitesimal rigid motions of (translations, rotations). The basic theorem is as follows.
Theorem 2.1 (e.g. [11])
A framework (G,p) with |V (G)|>d is infinitesimally rigid in if and only if
If (G,p) is infinitesimally rigid and satisfies |E(G)|=d|V (G)|−(^{d+1}_{2}) , we say that (G,p) is isostatic, meaning that it is minimally rigid. The notion of minimal rigidity also corresponds to the idea of a framework which is independent, meaning that the rows of the rigidity matrix are linearly independent. We elaborate on this idea in the subsequent section.
We remark finally that the rigidity of frameworks is a generic property: for almost all configurations p of a graph G, the framework (G,p) will be either infinitesimally rigid or infinitesimally flexible. In particular, we say that a generic position p of the graph G is one such that all minors of R(G,p) that have determinants which are not identically zero have non-zero determinant. This yields an open dense set of generic positions for a given graph G. We say that a graph G is generically rigid if it is infinitesimally rigid at all generic positions p. There are other ways to define generic; for example, we may demand that the coordinates of the vertices of G be algebraically independent over the rationals. In this case, the set of generic configurations is dense but not open.
The preceding definitions and notions are entirely standard. For further details, see [8–10] or [11].
(b) Bar–joint periodic orbit frameworks on the fixed torus
To describe periodic frameworks, we use the language of gain graphs (also known as voltage graphs [12]). A gain graph is a finite multi-graph G whose edges are labelled invertibly by the elements of a group. Suppose the edges of G are labelled by elements of , with the function . We say that the pair 〈G,m〉 is a (bar–joint) periodic orbit graph, for reasons that will soon become clear (figure 1a). The vertices of 〈G,m〉 are simply the vertices of the graph G. The edges of 〈G,m〉 are recorded e={v_{i},v_{j};m_{e}}, where . Since the edges are labelled invertibly by elements of , it follows that the edge e can equivalently be written
From the periodic orbit graph 〈G,m〉, we may define the derived periodic graph G^{m} which is the (infinite) graph whose vertex and edge sets are given by and , respectively (figure 1b) . If v_{i} is a vertex of 〈G,m〉, we say that is the orbit of v_{i} in G^{m}. Similarly, if e={v_{i},v_{j};m_{e}} is an edge of 〈G,m〉, then the orbit of edges in G^{m} corresponding to e is given by
Throughout this paper, we are concerned with periodic frameworks with a fixed periodic lattice, or, equivalently, orbit frameworks on a fixed torus, which we denote . By this, we mean the quotient space , where L is a d×d matrix we call the lattice matrix. The lattice matrix can be viewed as a set of translations under which a periodic framework is invariant. In fact, it has been demonstrated that infinitesimal rigidity is invariant under affine transformations [2,3], and as a result it is sufficient to consider frameworks on the unit lattice (L=I_{d×d}) as representatives of all periodic orbit frameworks. We henceforth use as the fixed torus. We may equivalently think of as the interval [0,1]^{d} with boundaries identified. We will find it convenient to use the interval [0,1)^{d} as a unit cell (typical tile) of a tiling of , and thus every position on the torus can be identified with a position in the interval [0,1)^{d}.
When we assign specific geometric positions on the fixed torus to the vertices of 〈G,m〉, we call the resulting object a periodic orbit framework (on ), which we denote (〈G,m〉,p), with , and p(v_{i})≠p(v_{j}) if e={v_{i},v_{j};m_{e}}∈E〈G,m〉. This in turn corresponds to the derived periodic framework, (G^{m},p^{m}), where the positions of the vertices are given by
In [13], we showed that every infinite periodic framework in the sense of Borcea & Streinu [2] can be represented as the derived periodic framework corresponding to a periodic orbit framework on the torus. The approach differs in terms of motions, which we shall now describe.
An infinitesimal motion of a periodic orbit framework (〈G,m〉,p) on is an assignment of velocities to each of the vertices, , such that for each edge e={v_{i},v_{j};m_{e}}∈E〈G,m〉. Such an infinitesimal motion instantaneously preserves the lengths of all of the bars of the framework. An infinitesimal motion is called trivial if it in fact satisfies for all triples {v_{i},v_{j};m_{e}}, . For any periodic orbit framework (〈G,m〉,p) on , there will always be a d-dimensional space of trivial infinitesimal motions of the whole framework, namely the space of infinitesimal translations. Rotations are no longer trivial motions, since we have fixed a representation of the lattice (and therefore of the torus ).
Suppose u is an infinitesimal motion of (〈G,m〉,p) on . We can translate this to an infinitesimal motion of (G^{m},p^{m}) in in the following way. Let be given by In other words, all vertices in the orbit corresponding to the vertex v_{i}∈V (G) have the same infinitesimal motion. This is in contrast to motions of (〈G,m〉,p) on a variable torus. In that setting, the motion assignment on (i,z) will depend on . In particular, the velocities of the vertices of (G^{m},p^{m}) are allowed to be infinitely large.
The vector space of all infinitesimal motions of (〈G,m〉,p) on is given by the kernel of the periodic rigidity matrix, R((〈G,m〉,p)). This is the |E|×d|V | matrix with one row for each edge e={v_{i},v_{j};m_{e}}∈E〈G,m〉 as follows: where the non-zero vector entries occur in the columns corresponding to vertices v_{i} and v_{j}, respectively.
There is always a d-dimensional space of trivial solutions to this matrix, namely the infinitesimal translations. We have the following version of theorem 2.1 for periodic orbit frameworks.
Theorem 2.2 [13]
A periodic orbit framework (〈G,m〉,p) is infinitesimally rigid on the fixed torus if and only if the rigidity matrix R(〈G,m〉,p) has rank d|V (G)|−d.
If (〈G,m〉,p) is infinitesimally rigid on and satisfies |E(G)|=d|V (G)|−d, we say that (〈G,m〉,p) is minimally rigid on .
If a set of rows of the rigidity matrix are linearly independent, we say that the corresponding edges are independent. Note then that minimal rigidity corresponds to the situation where the framework is infinitesimally rigid, and all edges of the framework are independent. For finite frameworks, this combination is known as isostatic; however, we avoid the term isostatic in the periodic context, for the reasons discussed in [14].
If a framework (〈G,m〉,p) contains loop edges, then those edges are automatically dependent. For this reason, we usually assume that periodic bar–joint orbit graphs 〈G,m〉 do not possess loops, since they are always redundant, meaning dependent in R((〈G,m〉,p)).
As for finite frameworks, if G is disconnected, then 〈G,m〉 is automatically infinitesimally flexible on . Note, however, that G may be connected, but the derived periodic framework G^{m} may be disconnected, as in the case of the two-vertex, two-edge graph where the edges are labelled by (0,0) and (1,0), respectively. Despite the disconnection of G^{m}, the periodic orbit graph 〈G,m〉 is nevertheless infinitesimally rigid on the two-dimensional fixed torus , which provides an indication of the structure forced by working on the fixed torus.
Similar to the situation for finite bar–joint frameworks, we may define a notion of a generic position of the vertices of (〈G,m〉,p) on (as represented by the interval [0,1)^{d}). That is, we say that p is generic if all minors of R((〈G,m〉,p)) that have determinants which are not identically zero have non-zero determinant. We say that the periodic orbit graph 〈G,m〉 is generically rigid if it is infinitesimally rigid at all generic positions p on .
We remark that to record a rigidity matrix for frameworks with a variable lattice, one must add extra columns. See [2,4] or [3] for details.
(c) Finite body–bar frameworks
Roughly speaking, a (finite) body–bar framework is a collection of bodies linked together with rigid bars. In defining body–bar frameworks more precisely, we follow the approach of Connelly et al. [15]. The bodies of a body–bar framework consist of collections of vertices, with each body joined to some of the other bodies by disjoint bars. Each body is assumed to be an isostatic finite bar–joint framework, although the details of the specific isostatic frameworks are unimportant, provided that the framework spans an affine space of dimension d−1 or greater. A generic body–bar framework is one where all of the vertices of all of the bodies are generic, in the sense of §2a. A multi-graph H records the connections between the bodies (H is permitted multiple edges, but no loops), and each vertex of H represents a body.
When we wish to explicitly refer to the vertices of a particular body, we use the graph G_{H}, which is the multi-graph H in which each vertex has been replaced with an isostatic graph, creating an isostatic bar–joint framework. G_{H} is indeed a simple graph with no multiple edges, because any two edges connecting a pair of bodies must have distinct vertices. Since every finite body in has (^{d+1}_{2}) degrees of freedom, and there is a (^{d+1}_{2}) -dimensional space of trivial motions of any body–bar framework, a body–bar framework is called minimally rigid if it satisfies |E(H)|=(^{d+1}_{2}) |V (H)|−(^{d+1}_{2}) . The following result of Tay characterizes the generic rigidity of body–bar orbit frameworks in d-dimensions.
Theorem 2.3 [5]
A multi-graph H is generically rigid as a body–bar framework if and only if the edges of H admit a decomposition into (^{d+1}_{2}) edge-disjoint spanning trees.
(d) Body–bar periodic orbit frameworks
We now define our main object of interest, body–bar periodic orbit graphs, which provide a recipe for periodic body–bar frameworks. Let H be a multi-graph, which is now permitted to have both multiple edges and loops. Let be a map on the directed edges of H. The pair 〈H,m〉 is called a body–bar periodic orbit graph, where the labelled edges provide a description of how the edges of H ‘wrap’ around the d-dimensional fixed torus (figure 2a). The vertices of 〈H,m〉 are denoted B_{1},B_{2},… and the edges are given by e={B_{α},B_{β};m_{e}}.
Just as for bar–joint periodic orbit graphs, for a periodic body–bar orbit graph 〈H,m〉 we may define a derived periodic body–bar graph H^{m} which is an infinite periodic structure (figure 2b). Suppose 〈H,m〉 is a periodic body–bar orbit graph. We define the derived periodic body–bar graph H^{m} to be the infinite graph with vertex set and edge set (the ‘universal cover’ in the topological sense). If e={B_{α},B_{β};m_{e}} is an edge of E〈H,m〉, then the countably infinite set of edges forms an orbit of edges of H^{m}, connecting the orbit of the body B_{α} (denoted ) with the appropriate copy (depending on m_{e}) of the orbit of the body B_{β}.
When we wish to explicitly refer to the underlying bar–joint framework, we denote by 〈G_{H},m_{H}〉 the (bar–joint) periodic orbit framework obtained by replacing every vertex of H with a finite (i.e. not periodic) isostatic bar–joint framework. The map m_{H} will simply be m on the edges of H, and will map all other edges to the zero vector (these are the edges of the isostatic frameworks making up each body (vertex) of H).
Body–bar periodic orbit frameworks (〈H,m〉,q) are body–bar orbit graphs, together with a map q, which maps the vertices of 〈H,m〉 to bodies on , and the edges of 〈H,m〉 to bars on . We assume that each body spans an affine subspace of of dimension at least d−1, and furthermore that, up to translation, the body lies completely within the interval [0,1)^{d} (our representation of . This can also be expressed as a map p_{H} directly on the vertices of the induced bar–joint framework 〈G_{H},m_{H}〉.
An infinitesimal motion of the body–bar periodic orbit framework (〈H,m〉,q) can be defined as an infinitesimal motion of the underlying bar–joint framework (〈G_{H},m_{H}〉,p_{H}). That is, it is a map such that the lengths of all edges E〈G_{H},m_{H}〉 are infinitesimally preserved, for all edges e={v_{α,i},v_{β,j};m_{e}} in E〈G_{H},m_{H}〉 (which corresponds in turn to the edge {B_{α},B_{β};m_{e}} in E〈H,m〉).
An infinitesimal motion of (〈H,m〉,q) on is trivial if it is an infinitesimal translation. As for bar–joint periodic orbit frameworks, rotations are again not considered trivial motions in this conception, as described in §2b. (〈H,m〉,q) is infinitesimally rigid on if (〈G_{H},m_{H}〉,p_{H}) is infinitesimally rigid on , that is, if its only infinitesimal motions are trivial (translations).
Every body in has (^{d+1}_{2}) degrees of freedom. Similar to the situation for bar–joint periodic orbit frameworks on , there is always a d-dimensional space of trivial motions (corresponding to the unit translations in d directions). It follows that, for minimal rigidity of a body–bar periodic orbit framework on , we require exactly |E(H)|=(^{d+1}_{2}) |V (H)|−d edges.
Proposition 2.4
Let (〈H,m〉,q) be a d-periodic body–bar framework, with |E(H)|=(^{d+1}_{2}) |V (H)|−d. Then the induced bar–joint framework (〈G_{H},m_{H}〉,p_{H}) will have |E(G_{H})|=d|V (G_{H})|−d.
The proof is elementary.
Remark 2.5
Instead of replacing each vertex of H by an isostatic finite framework, we could alternatively replace each vertex of H with a minimally rigid periodic orbit framework. In this case, the new gain assignment m_{H} would inherit the gains on the periodic orbit frameworks corresponding to each body. We do not pursue this variation in the present work.
We say that the body–bar orbit framework (〈H,m〉,q) is generic on if the induced bar–joint framework (〈G_{H},m_{H}〉,p_{H}) is generic. That is, the attachment vertices (of the endpoints of the edges of H) and all other vertices added as part of the isostatic frameworks replacing the vertices of H are generic in the sense of bar–joint frameworks.
We say that the edges of a body–bar orbit graph 〈H,m〉 are (generically) independent if the corresponding edges of 〈G_{H},m_{H}〉 are independent as rows in the bar–joint periodic orbit matrix R(〈G_{H},m_{H}〉,p_{H}) for generic positions p_{H}. Note that the edges of any of the isostatic frameworks which make up the bodies will automatically be independent, since they correspond to generic isostatic frameworks.
In contrast to the situation for bar–joint periodic orbit frameworks, loops may be permitted to be independent in body–bar periodic orbit frameworks. The endpoints of the loop must correspond to distinct vertices in the underlying bar–joint framework (figure 2b). Each body may have up to (^{d+1}_{2}) −d independent loops on . Note also that, for bar–joint periodic orbit frameworks on a variable torus, loops are also possibly independent, but with more restrictions [3,4].
Remark 2.6
It may be desirable to define a rigidity matrix for periodic body–bar frameworks directly, without reverting to a bar–joint framework. One possible version uses the language of extensors and exterior algebra, as in White & Whiteley [16], or in the coordinatized presentation in [17]. A rigidity matrix for body–bar frameworks with a flexible lattice was described in [7], and a matrix for the fixed lattice could be deduced from this presentation if desired.
(e) Inductive constructions on three-dimensional bar–joint periodic orbit frameworks
Tay and Whiteley [18] outline several methods for generating generically rigid bar–joint frameworks (finite frameworks). Some of the original ideas and definitions date back to Henneberg [19], who proved that all generically rigid frameworks in can be generated by a sequence of vertex additions and edge splits. Building on the work of Tay and Whiteley, we now define periodic versions of these two moves, for three-dimensional bar–joint periodic orbit frameworks.
Vertex addition. Let 〈G,m〉 be a (bar–joint) periodic orbit graph. A periodic vertex addition (figure 3) is the addition of a single new vertex v_{0} to V 〈G,m〉, and the edges to E〈G,m〉, subject to the following restrictions:
(i) m_{0j}≠m_{0k} whenever v_{ij}=v_{ik},
(ii) if v_{i1}=v_{i2}=v_{i3}, then m_{ij}≠m_{ik}, and the vectors m_{i1},m_{i2},m_{i3} span a vector space of dimension at least 2.
Note that condition (i) simply ensures that no two edges connecting a single pair of vertices have the same gains, which would correspond to a pair of identical edges in G^{m}. The second restriction ensures that if all three edges connect vertex v_{0} with a single other vertex in 〈G,m〉, then the vertex addition does not produce a framework with degenerate geometry. For example, if the three gains m_{1},m_{2} and m_{3} are (1,0,0),(2,0,0) and (3,0,0), respectively, then the vertex addition will always add a vertex which is incident to a line, and therefore has a non-trivial motion. However, (1,0,0),(2,0,0) and (0,1,0) would be an example of a valid gain assignment.
Proposition 2.7
Let 〈G,m〉 be a (bar–joint) periodic orbit graph, with and let 〈G′,m′〉 be the orbit graph created by performing a vertex addition on 〈G,m〉, adding the vertex v_{0}. If 〈G,m〉 is generically rigid on then so is 〈G′,m′〉.
The proof of this fact is a straightforward extension of the proof of the two-dimensional version presented in [3], and we omit it.
Edge splitting. Let 〈G,m〉 be a periodic orbit graph, and let be an edge in E〈G,m〉. A periodic edge split 〈G′,m′〉 of 〈G,m〉 is a graph with vertex set V 〈G,m〉∪{v_{0}} and edge set consisting of all of the edges of E〈G,m〉 except e, together with the four additional edges where the gains are subject to the same restrictions as for vertex additions (figure 4). Precisely:
(i) if any two of the added edges have the same endpoints, their gains are distinct;
(ii) if any three of the added edges have the same endpoints, then each pair of edges satisfies (i), and the gain space of the three-edge, two-vertex graph has dimension at least 2.
Proposition 2.8
Let 〈G,m〉 be a periodic orbit graph, with and let 〈G′,m′〉 be the orbit graph created by performing an edge split on 〈G,m〉, adding the vertex v_{0}. If 〈G,m〉 is generically rigid on then so is 〈G′,m′〉.
Proof.
Let p be a generic position of 〈G,m〉, and let (G^{m},p^{m}) be the derived periodic framework in . Suppose we wish to perform the edge split on the edge e={v_{1},v_{2};m_{e}}, which would add the edges listed above.
We begin by performing a vertex addition on 〈G,m〉, adding vertex v_{0} and the three edges We select a position p_{0} for the vertex v_{0} on so that p_{0} lies on the line of the edge e on . Equivalently, the orbit of vertices in V (G^{m},p^{m}) lies along the lines of the orbit of edges (e,z) in E(G^{m},p^{m}).
We now use proposition 2.9 to replace the pair of edges with the pair which maintains generic rigidity and completes the proof. □
The following proposition is a restricted version of the isostatic substitution principle (e.g. [18]). It is sometimes referred to as the ‘triangle exchange’, from the operation on a collinear triangle.
Proposition 2.9
Let (〈G,m〉,p) be a generically rigid periodic orbit framework on with edge e={v_{1},v_{2};m_{e}}. Let p_{0} be a point on the line connecting the positions p_{1} and p_{2}+m_{e}. Then replacing the pair of edges with the pair will result in another generically rigid periodic orbit framework on .
Proof.
Since we have chosen the point p_{0} so that the triple of edges is collinear, these edges therefore form a dependent set of rows in the rigidity matrix. Hence, we may replace any pair for any other pair. □
Remark 2.10
The preceding definitions of vertex addition and edge split are natural in the following sense: they correspond to ‘classical’ vertex additions and edge splits on the (infinite) derived periodic framework (G^{m},p^{m}), in which each move adds/modifies whole orbits of vertices and edges. In addition, proposition 2.9 corresponds to replacing whole orbits of edges with other (equivalent) orbits in (G^{m},p^{m}).
3. Statement of main result
Before we state our main result, we require one final definition, namely that of the gain space of a gain graph.
The cycle space of G is the subspace of the edge space of a graph (see [20]) spanned by the (edge sets of the) cycles of G. Suppose 〈G,m〉 is a gain graph where is the cycle space of the (undirected) graph G. The net gain on a cycle of G is determined by summing the gains on each edge of a participating edge, taking the positive or negative gain depending on the direction of traversal. The gain space is the vector space (over ) spanned by the net gains on the cycles of . Depending on the context, we will write either or , where Y ⊆E(G) is a subset of the edge set of G.
In contrast to cycles in directed graphs, we permit re-direction of the edges of a gain graph provided that they are accompanied by a relabelling of the gains on the edges as well. In this way, we should think of cycles in the gain graph as corresponding one-to-one with cycles in the base graph.
We may now state our main result.
Theorem 3.1
〈H,m〉 is a generically minimally rigid body–bar periodic orbit graph on if and only if
|E(H)|=6|V (H)|−3;
for all non-empty subsets Y ⊂E(H) of edges ∗
We remark that we have chosen to state this result in terms of edge-induced subgraphs to distinguish it from the usual approach in rigidity theory of using vertex-induced subgraphs.
Observe that the first two terms of the sparsity expression (∗) correspond to necessary conditions for the independence of a finite body–bar framework. Recall that for such a framework to be independent we must have that |Y |≤6|V (Y)|−6 for all Y ⊆E(G). In this way, (∗) indicates that we may add additional edges (given by the term ), depending on the dimension of the gain space, . Furthermore, it is clear that any graph satisfying conditions 1 and 2 will have the property that all vertex-induced subgraphs, for X⊆V (H), will satisfy |E(X)|≤6|X|−3. That is, H is a [6,3]-graph (see §4a).
To further motivate this result, we consider an example.
Example 3.2
For minimally rigid finite body–bar frameworks, there may be at most six edges between any two bodies (figure 5a). For minimally rigid body–bar periodic orbit frameworks, there may be at most nine edges between any two bodies (figure 5b). By (∗), labels on these edges must have the property that |〈m_{1},m_{2},m_{3}〉|≥2, and |〈m_{i},m_{j}〉|≥1. For example, (1,0,0),(1,0,0),(0,1,0) is a valid labelling of m_{1},m_{2} and m_{3}, respectively. In this case, any set Y of seven or eight edges will have , and the full set of nine edges has .
Remark 3.3
Counterintuitively, we do not require that for rigidity. In other words, it is possible for a disconnected derived periodic body–bar framework (H^{m},q^{m}) to be infinitesimally rigid in . This is because of the extra constraints imposed by the fixed lattice or torus.
Furthermore, it should be noted that the choice of unit cell (equivalently, the way we represent a periodic framework by an orbit graph) determines rigidity in this context. For instance, the single vertex is generically rigid on , but the orbit graph consisting of two disconnected vertices is not. The two-vertex graph can be obtained from the single-vertex graph by a cover of the original. This is indeed one of the limitations of the fixed torus model, but related problems remain a challenge in any reduction of infinite periodic structures to a finite representative graph.
Theorem 3.4
〈H,m〉 is a generically rigid body–bar periodic orbit graph on if and only if 〈H,m〉 contains a subgraph 〈H′,m′〉 which is generically minimally rigid on .
Since the rigidity of a periodic body–bar orbit framework is determined by the rank of a matrix, the preceding theorem follows from basic linear algebra.
(a) Necessary conditions for generic rigidity on
To see why the conditions of theorem 3.1 are necessary, we use an earlier result from the rigidity of bar–joint periodic orbit frameworks on , as outlined by theorem 3.5. Recall that the minimal number of edges for a periodic orbit bar–joint framework to be infinitesimally rigid on is d|V |−d.
Theorem 3.5 [13]
Let 〈G,m〉 be a minimally rigid bar–joint framework on . Then for all subsets of edges Y ⊆E, 3.1
After converting our body–bar orbit graph 〈H,m〉 to a bar–joint orbit graph 〈G_{H},m_{H}〉, we see that the necessary conditions for bar–joint and body–bar orbit graphs on are equivalent. We remark that the first two terms in (3.1) are simply the necessary conditions for the independence of a finite periodic bar–joint framework in d-dimensions: |Y |≤d|V (Y)|−(^{d+1}_{2}) . When , (3.1) becomes |Y |≤d|V (Y)|−d. See [13] for a detailed proof.
4. Sufficient conditions for generic rigidity on
The proof of the sufficiency of theorem 3.1 is more challenging. We use the following approach. Section 4a describes a result of Fekete and Szego which provides an inductive characterization of the combinatorial class of graphs in which we are interested. Section 4b shows that modifying these inductive moves (edge pinches) to incorporate gains preserves the generic rigidity of the corresponding body–bar orbit frameworks on . Finally, §4c provides the main combinatorial step, in proving that all gain graphs which satisfy the sparsity condition (∗) can be generated through a sequence of gain-modified edge pinches from an appropriate starting graph, which is a direct modification of the techniques of Fekete and Szego.
(a) Inductive constructions for [6,3]-graphs
Let H be a multi-graph. For a subset of vertices X⊂V (H), let i_{H}(X) denote the number of induced edges on the vertex set X. We say that H is [k,ℓ]-sparse if |i_{H}(X)|≤k|X|−ℓ holds for every X⊂V (H). H will be called a [k,ℓ]-graph if, in addition to being [k,ℓ]-sparse, H also satisfies |E(H)|=k|V (H)|−ℓ. In some terminology [k,ℓ]-graphs are known as [k,ℓ]-tight graphs (e.g. [21]).
We summarize a result of Fekete & Szego [22], first by introducing inductive graph constructions called edge pinches. Let 0≤j≤n≤k. An edge pinch, denoted K(k,n,j), consists of the following: choose j edges of H, and pinch them into a new vertex, z. Link z with other vertices of H with k−n new edges, and place n−j loops on the vertex z (figure 6). Following the edge pinch, the new graph has k more edges than the original, and the new vertex has degree k+n.
The single vertex graph with x loops will be denoted P_{x}.
The main result of [22] is the following.
Theorem 4.1 [22]
Let H be a multi-graph and let 1≤ℓ≤k. Then H is a [k,ℓ]-graph if and only if H can be created from P_{k−ℓ} with edge pinches K(k,n,j), where j≤n≤k−1, and n−j≤k−ℓ.
In §4c, we will state and prove a modified version of this result for [k,ℓ]=[6,3] that follows the proof of Fekete and Szego. We first describe gain-modified versions of edge pinches, and prove that they preserve the generic rigidity of body–bar periodic orbit frameworks on .
We remark that Lee & Streinu [21] independently characterized the same range of [k,ℓ]-graphs, and also have a Henneberg-type result. We do not use their methods here.
(b) Modified edge pinches preserve generic rigidity of body–bar periodic orbit frameworks in three dimensions
We now describe gain-modified versions of edge pinches in three-dimensions, which are edge pinches on body–bar orbit graphs 〈H,m〉 (). A gain-modified edge pinch K*(6,n,j) on 〈H,m〉 is an edge pinch K(6,n,j) on H to form the graph H*, together with an extension m* of the gain assignment m to the new edges, such that
(i) any pinched edge e={B_{α},B_{β};m_{e}} becomes the two edges {B_{α},B_{0};m_{e1}} and {B_{0},B_{β};m_{e2}}, where m_{e1}+m_{e2}=m_{e};
(ii) any subset of the new edges (including the pinched edges) satisfies (∗).
Condition (ii) ensures that, for example, loops on the new vertex z have gain assignments which satisfy the necessary conditions of theorem 3.1.
Theorem 4.2
Let 〈H,m〉 be a periodic body–bar orbit graph, and suppose 〈H′,m′〉 is the orbit graph resulting from performing the edge pinch K*(6,n,j) on 〈H,m〉. If 〈H,m〉 is generically rigid on then so is 〈H′,m′〉.
Proof.
The proof follows the following two steps. It is related to the arguments appearing in the paper of Connelly et al. [15].
j=0;
1≤j≤5.
Step 1. j=0 (body addition) Note that, when j=0, we are not splitting any edges. Instead, we are simply adding a new vertex to H (a body), which has between 0 and 3 loops. For bar–joint frameworks, this type of move is usually called a vertex addition (e.g. [18]), but for our purposes we will think of it as a body addition, since each vertex in H represents a body in a periodic orbit framework (〈H,m〉,q) on .
Let 〈H,m〉 be the body–bar orbit graph, and suppose we are performing the edge pinch K*(6,n,0), where 0≤n≤3. We first convert 〈H,m〉 to the induced bar–joint framework 〈G_{H},m_{H}〉. We now have four cases, for the four possible values of n; see table 1. We perform rigidity-preserving moves on the bar–joint frameworks, as described in §2e. The first column of table 1 is the ‘target’, meaning that it is this body–bar framework 〈H′,m′〉 that we wish to create. The three other columns depict moves on the underlying bar–joint framework 〈G_{H},m_{H}〉.
All four cases follow the same formula (vertex addition, edge split, vertex addition) as illustrated in table 1. In the case that m=1 or 2, we can perform the pictured edge split, since we know that m_{6}≠(0,0,0) (as the gain on the loop in our target). In the case that m=3, and we are performing the pinch K*(6,3,0), we note that, among the three loops with gains m_{4},m_{5} and m_{6}, we must have at least two distinct gains. That is, we may assume without loss of generality that m_{4}≠m_{5}≠(0,0,0). This makes the edge split we perform a valid one. Let the bar–joint periodic orbit graph resulting from this sequence of moves be denoted 〈G_{H}′,m_{H}′〉.
The final step in all cases is to recognize the triangle with all edges having zero gains as an isostatic graph in spanning a two-dimensional affine subspace, which permits us to treat this triangle as a body, and convert 〈G_{H}′,m_{H}′〉 back to a body–bar framework 〈H′,m′〉. That is, we add a new vertex to the vertices of the graph H to form V (H′), and any edges with non-zero gains that are adjacent only to this triangle become loops on the new body. Since we preserved the generic rigidity of the induced bar–joint framework at every stage, the resulting body–bar orbit graph 〈H′,m′〉 is generically rigid on too.
Step 2. 1≤j≤5 (all other edge pinches) Suppose we are splitting the edges {B_{α1},B_{β1};m_{1}},…,{B_{αj},B_{βj};m_{j}}, 1≤j≤5, and performing the edge split K*(6,n,j). We will think of this operation geometrically in terms of the derived periodic framework (H^{m},q^{m}). That is, we are splitting the following orbits of edges in H^{m}:
Performing a body addition (as in step 1) to (〈H,m〉,q) corresponds to adding a new orbit of bodies to (H^{m},q^{m}). We claim that we can perform a body addition so that:
— the new body lies within a translate of the unit cell, and
— j of the edges adjacent to the new body lie along the lines of the edges we wish to split.
To see this, select j generic points, one from along the line of each edge to be split. Because the set of generic points is dense, we may ensure that these j points lie within one cell. Since the j points are generic, we may define an isostatic bar–joint framework on these vertices (possibly adding other vertices if j=1,2), which corresponds to a body in (〈H,m〉,q). This body lies within the unit cell, since all edges have gain (0,0,0). Furthermore, since this is a body addition, the resulting framework 〈H*,m*〉 is also generically rigid.
Let this body addition add 6−n additional edges that are not among those to be split, and n−j loops, which are labelled as desired (figure 7). The j edges which lie along the lines of the edges to be split need not have the same gains as the edges to be split, as illustrated. In fact, if we wish to create a graph with edges we may always obtain this as an edge pinch of a graph with the edge {B_{1},B_{2};m_{a}+m_{b}}.
We complete the edge pinch by noting that, by proposition 2.9 applied to the corresponding orbits of edges in (H^{m},q^{m}), replacing the pair of edges in 〈H,m〉 with the pair results in a generically rigid framework. Replacing every such pair in 〈H*,m*〉 (there are j of them), we obtain the generically rigid framework 〈H′,m′〉 which is obtained from 〈H*,m*〉 by the desired edge pinch, and the claim holds. □
(c) Modified edge pinches generate the correct class of graphs
The main result of this section is as follows.
Theorem 4.3
Let 〈H,m〉 be a [6,3]-graph with the property that all non-empty subsets Y ⊂E of edges satisfy Then 〈H,m〉 can be obtained from 〈P_{3},m*〉, where by a sequence of gain-modified edge pinches.
The proof of this result is based on the proof of theorem 4.1, as recorded in [22], with a few modifications.
By splitting off edges of the gain graph 〈H,m〉, we mean the operation of replacing the edges e={u,v;m_{e}} and f={u,w;m_{f}} with the new edge h={v,w;m_{f}−m_{e}}, which we call the split edge. The resulting graph we denote by 〈G^{ef},m^{ef}〉, where G^{ef}=(V,E−e−f+h), and m^{ef} is the original gain assignment modified to include the new gain on the added edge h.
Theorem 4.4 (analogous to [22, theorem 2.2])
Let 〈H,m〉, H=(V +s,E) be a [6,3]-graph satisfying (∗), and let n,j be integers such that deg_{H}(s)=6+n, i_{H}(s)= n−j, where j≤n≤6, and n−j≤3. Then we can split off j pairs of edges so that, after deleting s, the resulting graph is a [6,3]-graph which also satisfies (∗).
For brevity, we say that a [6,3]-graph which satisfies (∗) is a [6,3]--graph. If 〈H,m〉, where H=(V +s,E), is a [6,3]--graph and e,f are edges in E〈H,m〉, then splitting off e and f is called admissible if 〈H^{ef},m^{ef}〉 is also a [6,3]--graph. Finally, we define Some authors have used a similar measure with the name ‘deficiency’, since b_{H} describes how many edges can be added while maintaining independence. Note that a body–bar orbit graph 〈H,m〉 is a [6,3]--graph if and only if g_{H}(Y)≥0 for all subsets of edges Y ≠∅, Y ⊆E(H).
To prove theorem 4.4, we make use of the following lemma.
Lemma 4.5 (analogous to [22], lemma 2.3])
Let 〈H,m〉, H=(V +s,E+{e,f}), be a [6,3]--graph, where e={s,u;m_{e}}, f={s,v;m_{f}} are edges incident to s, (u,v∈V). Then the pair e,f is admissible if and only if with u,v∈V (X), such that where h={u,v;m_{f}−m_{e}} is the split edge.
We omit the proof. See figure 8 for examples of admissible and non-admissible pairs of edges.
The following proposition is central to the proof of theorem 3.1.
Proposition 4.6
Let 〈H,m〉 be a [6,3]--graph, and let X and Y be subsets of edges of H. If b_{H}(X)=b_{H}(Y)=0, then b_{H}(X∪Y)=0 too.
Proof.
We first note that if X∩Y =∅, then the claim is trivial. We therefore assume that X∩Y ≠∅. We also remark that and therefore we need not consider the case separately from . We thus take cases as follows.
Case a: . Since b_{H}(X)=b_{H}(Y)=0, we have |X|=6|V (X)|−6 and |Y |=6|V (Y)|−6. It must also be the case that , and therefore 4.1
We have 4.2Together, (4.1) and (4.2) imply that Since 〈H,m〉 is a [6,3]--graph, 6|V (X∪Y)|−6<|X∪Y | if and only if . We will show that , and therefore 6|V (X∪Y)|−6=|X∪Y |, and b_{H}(X∪Y)=0, as desired.
Suppose towards a contradiction that . Then |X∪Y |≤6|V (X∪Y)|−4, and, by (4.2), 4.3
For a cycle to be created with non-trivial gain, the intersection V (X∩Y) must contain at least two vertices, since any such cycle must contain edges from both X and Y . It follows that 4≤|X∩Y |, and the intersection is non-trivial. Furthermore, the intersection must be connected. (Suppose that X∩Y is disconnected, into say E_{1} and E_{2}. We must have |E_{i}|≤6|V (E_{i})|−6, and therefore |E_{1}|+|E_{2}|≤6(|V (E_{1})|+|V (E_{2})|)−12, but this contradicts (4.3).)
Suppose that a non-zero cycle is created containing a,b∈V (X∩Y). In the simplest case, the cycle consists of a single sequence of edges from X, followed by a single sequence of edges from Y (figure 9). We will treat other cases separately. Suppose that the cycle is as follows C=a,C_{X},b,C_{Y},a, where C_{X} is a path of vertices and edges in X and C_{Y} is a path of vertices and edges in Y . Suppose further that the path C_{X} has gain m_{X}, and the path C_{Y} has gain m_{Y}. Since the intersection (V (X∩Y),X∩Y) is connected, there is a path from a to b within the intersection. Suppose this path has gain m_{int}. Then we may write the cycle a,C_{X},b,C_{Y},a as a,C_{X},b,−C_{int},a,C_{int},b,C_{Y},a. But note that the cycle a,C_{X},b,−C_{int},a is completely contained in the edge set X, hence must have net gain zero. Similarly, a,C_{int},b,C_{Y},a is completely contained in the edge set Y , hence must have net gain zero. It follows that the net gain of the cycle a,C_{X},b,C_{Y},a is
It is a small extension to include cases where the cycle alternates between edges in X and edges in Y more than once (figure 10). The cycle a,C_{1},c_{1},C_{2},c_{2},C_{3},b,C_{Y},a can also be written as the sum of cycles in X and cycles in Y , Here, the first and third closed cycles at a have net gain 0 since they are completely contained in X, and the second and fourth closed cycles at a have net gain 0 because they are completely contained in Y . We have shown that it is not possible to have any cycles in X∪Y with non-zero gain, hence we must have , and therefore |X∪Y |=6|V (X∪Y)|−6 and b_{H}(X∪Y)=0, as desired.
Case b: . Since b_{H}(X)=b_{H}(Y)=0, we have |X|=6|V (X)|−4 and |Y |=6|V (Y)|−4. Then 4.4Now suppose that . Then |X∩Y |≤6|V (X∩Y)|−6. Then by (4.4), 6|V (X∪Y)|−2≤|X∪Y |, which is a contradiction, since no subgraph of a [6,3]-tight graph may satisfy this. Therefore, it must be the case that (it cannot be greater than 1, since it is a subset of both X and Y). Hence, Is it possible that (or 3)? We claim that it is not possible.
First note that since , we may write . That is, the gain space of X∩Y is generated by the gain . However, since X∩Y is a subset of both X and Y , each of which also have gain spaces of dimension 1, it follows that too.
The rest of the argument is similar to that in case a. Reconsidering figure 10 for this case, we obtain the cycle where . Hence, the net gain on this cycle is (k_{1}+k_{2}+k_{3}+k_{Y})m_{0}, which is clearly contained in 〈m_{0}〉. It is not possible, therefore, that . It follows that , and thus b_{H}(X∪Y)=0, as desired.
Case c: .
Since b_{H}(X)=b_{H}(Y)=0, we have |X|=6|V (X)|−3 and |Y |=6|V (Y)|−3. In this case, the fact that b_{H}(X∪Y)=b_{H}(X∩Y) follows directly from a lemma of Fekete and Szego, as follows.
Lemma 4.7 ([22, lemma 2.3])
If H is a [6,3]-tight graph, then b_{H}(X)=b_{H}(Y)=0, and X∩Y ≠∅ implies that b_{H}(X∪Y)=b_{H}(X∩Y)=0.
Case d: . In this case, |X|=6|V (X)|−6, and |Y |=6|V (Y)−4. It follows that and . Hence, |X∩Y |≤6|V (X∩Y)|−6. We have 4.5We claim that . Suppose towards a contradiction that . That is, a new cycle is created with a gain that is not generated by . Then |V (X∩Y)|≥2 (for a new cycle to be created), and the intersection is connected. Again we argue along the same lines as cases a and b. Considering figure 10, we write the cycle as Hence, the net gain on this cycle is (k_{2}+k_{Y})m_{0}, which is clearly contained in . It is not possible, therefore, that . It follows that , and thus b_{H}(X∪Y)=0, as desired.
Case e: (or 3). In this case, |X|=6|V (X)|−6, and |Y |=6|V (Y)−3. It follows that , and (or 3). Hence, |X∩Y |≤6|V (X∩Y)|−6. But since 4.6it follows that |X∩Y |=6|V (X∩Y)|−6, and |X∪Y |=6|V (X∪Y)|−3. Hence, b_{H}(X∩Y)=b_{H}(X∪Y)=0, as desired.
Case f: (or 3). In this case, |X|=6|V (X)|−4, and |Y |=6|V (Y)−3. It follows that , and (or 3). Hence |X∩Y |≤6|V (X∩Y)|−4. Again, since 4.7it follows that |X∩Y |=6|V (X∩Y)|−4, and |X∪Y |=6|V (X∪Y)|−3. Hence b_{H}(X∩Y)=b_{H}(X∪Y)=0, as desired. □
We also require the following proposition, which essentially says that if subsets X,Y ⊆E(H) prevent the splitting off of either of two pairs of edges, then so does the subset X∪Y .
Proposition 4.8
Let 〈H,m〉, H=(V (H)+s,E(H)+{e,f,g}), be a [6,3]--graph, where e={s,u;m_{e}}, f={s,v;m_{f}}, g={s,w;m_{g}} are edges incident to s. Let X and Y be subsets of E(H) such that u,v∈V (X), and v,w∈V (Y). Suppose h_{1}= {u,v;m_{f}−m_{e}} and h_{2}={v,w;m_{g}−m_{f}}(figure 11). If then b_{H}(X∪Y +h_{1})=b_{H}(X∪Y +h_{2})=−1 too.
Proof.
The proof of this proposition proceeds along the lines of the proof of proposition 4.6. In particular, we use cases a–f. We will prove one case in detail, the remaining cases are easily checked using the same methods.
Case d: .
What we must confirm is that adding either of the edges h_{1} or h_{2} to X∪Y results in an overbraced subgraph of H. In other words, we prove that adding h_{1} or h_{2} cannot increase the dimension of the gain space of X∪Y .
From the proof of proposition 4.6 we know that . Suppose towards a contradiction that . Then it must be the case that the added edge h_{1} participates in a cycle whose net gain is not contained in (figure 12). Furthermore, such a cycle must contain edges from both edge sets X and Y , and thus |V (X∩Y)|≥2. However, from the proof of proposition 4.6 we know that the intersection X∩Y is connected, and therefore we may break the cycle up into the sum of simple cycles, each of which is contained only in X or only in Y (figure 12). But we easily see that such a cycle has net gain km_{0}, , which is the contradiction.
A similar argument shows that too, and therefore as desired. □
With propositions 4.6 and 4.8 in place, the proofs of theorems 4.4 and 4.3 follow verbatim from the work of Fekete & Szego (see [22], theorems 2.2 and 1.6, respectively; lemma 4.5 and propositions 4.6 and 4.8 are analogous to [22], lemma 2.3). We sketch the principal ideas of both proofs, identifying the areas which require modification.
Proof of theorem 4.4 (sketch)
First note that if j=0, then G−s must be a [6,3]--graph. So, we assume that j≥1. Towards a contradiction, suppose that we cannot split off j edges so that the resulting graph is a [6,3]--graph. We split off as many edges as possible, say p<j to obtain the graph 〈H′,m′〉. Let e_{1}={s,v_{1};m_{1}},…,e_{α}={s,v_{α};m_{α}} be the non-loop edges incident to s in 〈H′,m′〉. By lemma 4.5, we know that for each pair of vertices v_{ν},v_{μ}, 1≤ν<μ≤α, there exists an edge set X_{νμ}⊂E(H′) such that
(a) v_{ν},v_{μ}∈V (X_{νμ}),
(b) b_{H}(X_{νμ})=0, and
(c) b_{H}(X_{νμ}+{v_{ν},v_{μ};m_{μ}−m_{ν}})=−1.
Using propositions 4.6 and 4.8 we may find such an edge set X_{〈H′,m′〉} that is maximal.
We consider all such 〈H′,m′〉 obtained by splitting off different sets of p pairs of edges, and we take so that is maximal. Let .
The remainder of the proof exactly follows [22]. We claim that there is a split edge e={v,w;m_{e}} in which is not in X, which is shown using a basic combinatorial argument that we do not reproduce here.
Fekete and Szego then use this fact to find a pair of edges which form an admissible splitting off, which contradicts the maximality of p. □
Proof of theorem 4.3 (sketch)
The ‘if’ part of this result is seen from the definition of gain-modified edge pinches.
To see the other direction, we proceed by induction on the number of vertices. The [6,3]--graph with only one vertex is 〈P_{3},m*〉, which we know is a [6,3]--graph by definition. Let 〈H,m〉 be an arbitrary [6,3]--graph with more than one vertex. Then it is not hard to show that there exists a node s with degree at most 11 (since H is [6,3]-tight).
Using a simple combinatorial argument, we find that letting , and j=n−i_{H}(s) (i_{H}(s) is the number of loops on s), we obtain n and j which satisfy the conditions of theorem 4.4 (see [22] for details).
Theorem 4.4 demonstrates that 〈H,m〉 is obtained from a smaller body–bar orbit graph 〈H′,m′〉 by a gain-modified edge pinch K*(6,n,j). By induction, we know that 〈H′,m′〉 can be constructed from 〈P_{3},m*〉, and hence 〈H,m〉 can be too. □
(d) Proof of main result (theorem 3.1)
Theorem 3.5 establishes the necessity of the two conditions for generic rigidity. Suppose 〈H,m〉 satisfies conditions 1 and 2 of our main theorem. By theorem 4.3, it can be built up from a single vertex with three loops by a sequence of gain-modified edge pinches. The single vertex is generically minimally rigid on , since a single body admits no non-trivial deformations on the fixed torus. By theorem 4.2, these gain-modified edge pinches preserve generic rigidity on , which completes the proof. □
5. Further work
As mentioned in the Introduction, it was previously conjectured that the results of the present paper hold for d-dimensional body–bar orbit frameworks [3]. That is, we claim the following.
Conjecture 5.1
〈H,m〉 is a generically minimally rigid body–bar framework on if and only if
— |E(H)|=(^{d+1}_{2}) |V (H)|−d;
— for all non-empty subsets Y ⊂E(H) of edges 5.1
It is evident that the approach of this paper does not immediately extend to this more general conjecture, since we have taken cases in the proofs of propositions 4.6 and 4.8, which are central to the proof of the main result. It is possible that some other method may prove useful in establishing the relevant results. Another possibility is that we abandon the approach of Fekete and Szego, and prove the result using an entirely different technique. In any case, we believe that the established result is a promising indication that the conjecture is true.
It is possible to check that the expression (5.1) gives rise to a submodular function on the set of oriented edges labelled by elements of . It then follows that the body–bar periodic orbit graphs 〈H,m〉 satisfying (5.1) form the independent sets of a matroid. We omit the details.
Other areas for further research may be the extension of these results to body–hinge frameworks, which provide yet another tool for studying molecular frameworks. The recent proof of the molecular conjecture [23] provides further motivation for this avenue of research. Finally, the development of algorithms based on the pebble game algorithm [24] for checking whether a given body–bar orbit graph satisfies the sparsity condition of theorem 3.1 would be of interest.
(a) Tubes and slabs
The paper of Whiteley [25] addresses the question of ‘fragments’ of periodic frameworks. That is, he considers finite pieces of periodic structures. As part of this set of questions he describes two types of fragments: tubes and slabs. Tubes are three-dimensional structures which are periodic in one direction. Slabs are three-dimensional structures which are periodic in two dimensions.
From the result presented in this paper, it is possible to obtain extensions to tubes and slabs which are not fragments. Tubes can be seen to correspond to periodic frameworks 〈H,m〉 with , and slabs correspond to those frameworks with . Adapting the present results to these contexts is the subject of a forthcoming joint paper.
Acknowledgements
The majority of this research was carried out at the Fields Institute for Research in Mathematical Sciences in Toronto, Canada. The author also wishes to thank Bernd Schulze and Walter Whiteley for their feedback, and the anonymous referees for several helpful suggestions and references.
Footnotes
One contribution of 14 to a Theo Murphy Meeting Issue ‘Rigidity of periodic and symmetric structures in nature and engineering’.
- © 2013 The Author(s) Published by the Royal Society. All rights reserved.