Rigid Circle and Sphere Packings. Part II: Infinite Packings with Finite Motion

Rubert Cunne//p Department of Mathematics Cornell University Ithaca, N Y 14853 Partially supported by N.S.F. grant, number MCS790251, as well as the I.H.E.S., Bures-sur-Yvette, France. Support was also given by the University of Dijon, Savoie University in France, and the MaxPlanck-Institute fur Mathematik at Bonn, West Germany. Subventionnb, en partie, par le N.S.F. (numero de subvention MCS-790251), ainsi que par I'I.H.E.S. a Bures-sur-Yvette, France. L'universitk de Dijon et I'universitb Savoie en France, ie Max-PlanckInstitute fur Mathematik a Bonn, en Allemagne de I'Ouest, ont aussi apporte leur appui. French translation: Traducrion frangaise : Jean-Luc Raymond RIGID CIRCLE AND SPHERE PA CKINGS PART 11 : INFINITE PACKINGS WITH FINITE MOTION ABSTRACT A packing Pof circles in the plane is called n-stable, for n = 1,2,. . . if every set of n circles is held fixed by the rest. P is called finitely stable if it is n-stable for every n = 1, 2,. . . For each of the 31 families of regular connected circle packings in the plane we classify which are finitely stable and which are not. For 3 of the cases when the families of packings are not finitely stable, it turns out that the smallest n for which they are not n-stable gets arbitrarily large, depending on a parameter of the family. I INTRDDUCTION Suppose we have a packing of circles in the plane. How should we define what it means for the packing to be stable? How do we calculate when this happens? One reason for such questions is the main result of part I [4]. Roughly, it says that locally maximally dense packings have rigid subpackings. Another reason is that solid crystal structures must have some sort of rigidity in order to be stable under external perturbations. JUXTAPOSITIONS RIGIDES RE CERCLES ET DE SPH€RES PARTIE 11 : JUXTAPOSITIONS INFINIES DE MOUVEMENT FIN1 Une juxtaposition P de cercles dans le plan est dite n-stable pour n = 1,2, . . . si tout ensemble de n cercles est tenu fixe par les autres. Pest destabilith finie si elle est n-stable pour tou t n = 1,2, . . . Parmi les 31 familles de juxtapositions regulieres connexes de cercles dans le plan que I'on a classifiees, certaines sont de stabilite finie, d'autres non. Dans 3 des cas de familles de judapositions qui ne sont pas de stabilite finie, il apparait que la plus petite valeur de n pour laquelle elles ne sont pas n-stables est arbitrairement grande, et depend d'un parametre de la famille. I INTRODUCTION Considerons une juxtaposition de cercles dans le plan. Commert peut-on definir ce que represente la stabilite pour la juxtaposition? Comment peut-on calculer les cas 00 cela se presente? Une des raisons de telles questions se situe dans le resultat principal de la partie I [4]. En gros, on y affirme que les juxtapositions localement maximalement denses possedent des sousjuxtapositions rigides. Une autre raison est que les structures d? 58 $? FIGURE 1 L. Fejes Toth has already defined a circle packing to be stable if each circle is fixed by its neighbors. This is particularly easy to calculate, but in many cases it happens that a packing is stable in his sense, but if even just three circles are allowed to move, the packing will “fallapart”. For example, the following packing, Figurel, hasthis property. So instead we choose a definition of stability which we believe to be more relevant. We say a circle packing P, in the plane, is n-stable if every set of n circles, in P, is held fixed by the rest of P. We say P is finitely stable if P is n-stable for all n = 1, 2, . , . Thus L. Fejes Toth’s definition of stability is what we call 1-stability. X The main object of part II is to classify, among the 31 types of connected regular packings in the plane, which are finitely stable and which are not. This is summarized in Table 1 (page 65). One reason for choosing these packings is that since they are regular, they are a potential source of crystal structures. A packing is regular if there is a congruence of the plane, taking the packing circles to packing circles, that takes any given circle to any other. U Another reason for choosing these packings is that they areasource of interesting examples. In particular, packings numbered 13, 14, and 15 have the property that they can be thought of as a kind of “bomb’: In each of these examples there is a parameter €I > 0 that describes a packing P,. Then there is an integer n(e) > 0 such that P, is n(e)-stable but not n(e)+l-stable. However, lim n(8) = m. If we choose 8 close to 0, we can imagine more and more circles being allowed to move until suddenly the whole packing collapses. e+o Basic to the analysis is the idea of a framework and the notion of rigidity and infinitesimal rigidity as discussed in part I. To any packing P we associate a graph Gp consisting of a vertex corresponding to each circle and an edge corresponding to each pair of cristal solide doivent posseder un certain type de rigidite afin de demeurer stables sous les perturbations externes. L. FejesToth adejadefini une juxtaposition stable de cercles comme une juxtaposition dont chacun des cercles est fixe parses voisins. C’est particulierement simple a calculer mais, dans plusieurs cas, il apparait qu’une juxtaposition stable selon son sens, pour laquelle on ne permet qu’a trois cercles de se deplacer, se (( desagregera.. A titre d’exemple, la juxtaposition de la figure 1 possede cette propriete. Ainsi, on adoptera plutBt une definition de stabilite qu’on croit &re plus appropriee. On dira qu’une juxtaposition P de cercles, dans le plan, est n-stable si tout ensemble de n cercles de Pest fixe par le reste de P. On diraque Pest de stabilite finie si Pest n-stable pour tout n = 1, 2,. . . Ainsi, la stabilite telle que definie par L. Fejes Toth correspond a ce qu’on appelle la 1-stabilitk. Le principal but de la partie II est I’identification, parmi les 31 types de juxtapositions connexes regulieres dans le plan, de celles qui sont de stabilite finie et de celles qui ne le sont pas. Ceci est resume dans le tableau 1 (p. 65). Une raison qui justifie le choix de ces juxtapositions est que puisqu’elles sont regulieres, elles constituent une source potentielle de structures cristallines. Une juxtaposition est reguliere s’il exite une isometrie du plan, faisant correspondre chaque cercle de la juxtaposition a un cercle de la juxtaposition, qui envoie tout cercle donne sur n’importe quel autre. Une autre raison du choix de ces juxtapositions est qu’elles sont la source d’exemples interessants. En particulier, les juxtapositions de numero 13,14 et 15 possedent la propriete de pouvoir &re interpretees comme une sorte de (( bombe )). Dans chacun de ces exemples, il existe un parametre 0 > 0 qui caracterise une juxtaposition Po. II existe alors un entier n(e) > 0 tel que P, est n(e)-stable mais n’est pas n(e)+l -stable. Toutefois, lim n(e) = W. e-+o 59 intersecting circles. The framework Gp(p) associates vertex i to pi, the center of circle i. p = (pl, . . .). It turns out that the rigidity of Gp(p) is determined by its infinitesimal rigidity, and thisallows us to apply many known techniques. For many of the 31 packings, at first sight, it does not seem obvious which arefinitelystableand which are not. 0ne’s”physical intuition” can sometimes be misleading. Even physical experiments have to be done carefully; the property of the bombs might be hard to detect. We believe that the tools presented here and in part I are a good first step in understanding the rigidity of packings. We thank Branko Grunbaum for pointing out many mistakes and making many comments in an earlier version of this paper. I CALCULA TlONS Suppose G( p) is a finite framework in Euclidean space Ed as described in part I, [l] or [3], but with k fixed vertices, n - k variable vertices, and e members, all struts. p= (pl, . . ., p,) is the sequence of vertices of G( p). That is, all distances between strut endpoints are not allowed to decrease. Suppose G( p) is infinitesimally rigid. Since all members are struts, this can only happen if there are sufficiently many fixed vertices (at least d+l), and the only trivial infinitesimal flexof G(p) is p’= 0, where p’= (p;, ..., pi). Thus p’= 0 is the only solution to the following system of inequalities: (p;-p;)-(p,-pj) 2 O,forli,jlamemberof G. This is a system of e linear inequalities in d(nk) variables, the coordinates of the variable vertices. This has only the zero solution only if d(n-k)tl I e. (2.1 1 Si on choisit 8 pres de 0, on peut imaginer que de plus en plus de cercles puissent se deplacer jusqu’a ce que soudainement la juxtaposition entiere s’effondre. A la base de cette analyse, on trouve le concept de charpente et les notions de rigidite et de rigidite infinitesimale presentes dans la partie I. A toute juxtaposition P, on associe un graphe Gpen faisant correspondre un sommet a chaque cercle et une arete a chaque paire de cercles d’intersection non nulle. La charpente Gp(p) associe le sommet i a p,, le centre du cercle i. p = (pl, . . .). II apparaTt que la rigidite de Gp(p) est determinee par sa rigidite infinitesimale et ceci permet d’appliquer plusieurs techniques connues. Plusieurs des 31 juxtapositions ne semblent pas, a premiere vue, pouvoir Btre classifiees de faqon evidente comme etant de stabilite finie ou non. L’ccintuition physique)) peut parfois induire en erreur. MBme les experiences physiques doivent etre realisees avec precaution; la propriete des bombes peut Btre difficile a deceler. Les outils presentes ici et dans la partie I apparaissent a I’auteur comme un bon pas vers la comprehension de la rigidite des juxtapositions. L’auteur remercie Branko Grunbaum pour avoir signale plusieurs erreurs et avoir emis plusieurs commentaires au sujet d’une version precedente de cet article. I/ CALCULS Supposons que G( p) soit une charpente finie dans I’espace euclidien Ed telle qu’on I’a decrite dans la partie I, dans [l] ou dans [3], mais possedant k sommets fixes, n - k sommets variables et e membres, tousdesetais. p= (p,, ...,p,,) estlasuitedessommets de G(p). Ainsi, aucune distance entre les extrernites d’un etai ne peut decroitre. Supposons que G( p) soit infinitesimalement rig ide. Puisque tous 60 It is helpful to rewrite (2.1) in terms of the average degree of a vertex 7 where - iv, V=Cv, is the degree of the i-th variable vertex in G. A vertex has degree v if it is a vertex of exactly v edges (also called members). i (n-k) ’ Supposethateachfixedvertexof G isonexactlyoneedgeof G. Then the number of vertex-edge incidences is 2e = (C v,) + k, where the sum is over variable vertices as before. Thus 2e = (nk) V+ k. (2.2) Combining this with (2.1) we get d(n-k)+1 I ‘/Z[(n-k)v+k], 2d-(%)s V Later in our applications to packings it will turn out that k will be much smaller than n, and so will then be not much smaller than 2 d. ses membres sont des etais, ceci ne peut se produire que s’il y a un nombre suffisamment grand de sommets fixes (au moins d+l); le seul mouvement infinitesimal de G(p) est p’= 0,oU p‘= ( p;, . . ., p;). Ainsi p’= 0 est la seule solution du systeme d’inequations suivant : (p; - pi). (pipj) 2 0, pour {i, jl membre de G. C’est un systeme de e inequations lineaires en d(nk) variables, les coordonnees des sommets variables. II ne possede que la solution nulle seulement si d(n-k)t1 2 e. (2.1 1 II est utile de reecrire (2.1) en fonction du degr6 moyen d’un sommet V, oh - iv, V=SI (n-k) OD v, est le degre du i-erne sommet variable de G. Un sommet est de degre v s’il est le sommet d’exactement v aretes (membres). Supposons que chaque sommet fixe de G soit sur exactement une arQte de G. Alors le nombre d’incidences sommet-ar8te est 2e = (C vi)+k, OD la somme parcourt les sommets variables comme precedemment. Ainsi 2e = (nk) V+ k. (2.2) En combinant ce resultat avec (2.1), on obtient d(n-k)+l 2 Vz[(n-k)V+k], 2d-(S)s V (2.3) Plus loin dans les applications aux juxtapositions, il apparaitra que k est beaucoup plus petit que n, et ainsi ne sera pas beaucoup plus petit que 2d. 61 Ill GRAM WITHSM AVERAGE DEGREE We can use the calculations of section II to eliminate as being rigid many graphs with low average degree 7. Theorem 3.7 Let G(p) be a connected (infinitesimal&) rigid strut graph in Ed where each variable vertex of G has degree d + 1, and each fixed vertex has degree 1. Then G is a tree. 1.e. there are no cycles in G. Proof Using the notation above, 7 = d+l. Then (2.2) implies, 2(ne) = 2n- (nk) (dt 1) - k = 2n- (nk) d-n+ kk (3.1 1 = n-(n-k)d. On the other hand, since G( p) is rigid, using (2.3) and 7 = dt 1, we get 2d- (x) k2 2 d+l , which simplifies to 2 I n-d(n-k). Combining (3.1) and (3.2) we get 2 I 2(n-e) or 1 5 n-e. Since G is connected, this implies G is a tree. 111 GRAPHES DE PETIT DEGREMOYEAT En utilisant les calculs de la section II, il est passible d’eliminer plusieurs graphes de petit degre moyen 7, ceux-ci etant rigides. Theor4me 3.7 Soit G( p) un graphe d’etais connexe (infinithimalement) rigide dans Ed, 00 chaque sommet variable de G est de degre d + 1 et chaque sommet fixe est de degr6 1. Alon G est un arbre. C’est-a-dire qu’il n’y a aucun cycle dans G. Ddmonstrafion Avec la notation introduite precedemment, on a v= d + 1. Alors, (2.2) implique - 2(ne) = 2n- (nk) (dt 1) - k = 2n- (nk) dn+ kk = n-(n-k)d. (3.1) D’autre part, puisque G(p) est rigide, en invoquant (2.3) et le fait que 7 = d +1, on obtient ce qu’on peut simplifier de la facon suivante: 2 I n-d(n-k). En combinant (3.1) et (3.2), on obtient 2 5 2(n-e) ou 1 I n-e. Puisque G est connexe, ceci implique que G est un arbre. (3.2) 62 FIGURE 2 In the plane E2 this says that if the degree of each variable vertex is 3, then there can be no cycles if G(p) is to be rigid. For example, the strut framework (Figure 2) is not rigid. Variable vertices are denoted by 0, fixed vertices by 0, and represent a strut. Note that in the above, there is no real loss of generality in assuming that the degree of each fixed vertex is 1. We can create afixed vertex for each edge that has some fixed vertex on it and regard each of these new fixed vertices as distinct in G but with the same position vectors pi in the framework G(p). or FIGURE 3 Alternatively, suppose i is afixed vertex of G, j is avariable vertex, and (i, j} is an edge of G. Then we can replace Ii, 11 with Ii: j} where i’ is another fixed vertex and put p,. anywhere on the ray from p, to pi in Ed, to get a new graph and a new framework that is infinitesimally rigid if and only if the original graph G(p) is. See Figure 3. Y w with est is replaced rernplack JI We can do the above process for each Ii, jl member in G for all j and then eliminate i. There is also a converse to Theorem 3.1. Namely if each variable vertexof G(p) isin the interioroftheconvexhullof itsdtl neighbors, the endpoints of G are the fixed vertices, and G is a tree, then G(p) is infinitesimally rigid. We omit the proof. Dans le plan E2, ce resultat affirme que si le degre de chaque sommet variable est egal a 3, alors il ne peut y avoir aucun cycle si G(p) doit itre rigide. Par exemple, la charpente d’etais de laligure 2 n’est pas rigide. Les sommets variables sont designes par 0, les sommetsfixes par., et ou I represente un etai. On note que dans ce qui predde, il n’y a pas de veritable perte de generaliti en supposant que le degre de chaque sommet fixe est egal a 1. On peut creer un sommet fixe pour chaquearhte possedant au moins un sommet fixe et interpreter chacun de ces nouveaux sommets fixes comme des sommets distincts dans G en conservant toutefois les mhmes vecteurs de position pi dans la charpente G( P)- Comme alternative, supposons que i soit un sommet fixe de G, j un sommet variable et Ii,jl une arhte de G. On peut alors remplacer {iJ par (i;j}, oh i’est un autre sommetfixe et pi. est place n’importe oh sur le rayon qui va de p, a pi dans Ed. On obtient un nouveau graphe et une nouvelle charpente qui est infinitesimalement rigide si et seulement si le graphe original G(p) I’est aussi. Voir la figure 3. Ce processus peut &re effectue sur chaque membre (i, jl de G pour tout j et on elimine ainsi i. II existe une reciproque au theoreme 3.1, En effet, si chaque sommet variable de G(p) se situe a I’interieur de I’enveloppe convexe de ses d+l voisins, que les extremites de G sont les sommets fixes et que G est un arbre, alors G(p) est infinitesimalement rigide. On omettra la demonstration. 63 IV THE 31 TYPES OF CIRCLE PACKINGS In the following we shall show representatives of the 31 types of regular connected circle packings in the plane. These are taken from the bookof L. FejesToth [6], butwe havechosenadifferent ordering so that related packings are nearto each other. See also Griinbaum and Shephard [7] for a description of the classification. In each diagram (Figure 4, pages 66-70) we first show the packing with the graph of the packing indicated as well. On this diagram we have indicated a rigid ordering, if it exists, assuming the boundary vertices are fixed. That is, by adding in the vertices of the associated rod framework to the fixed vertices in the order indicated, we get successively frameworks that are infinitesimally rigid. Each of the new vertices must be joined to at least two previous vertices such that all three do not lie on a straight line. See Lemma 6.2 of part I [4, p.51 I. Directly beside each of the 31 packings, we have indicated a reciprocal diagram, if it exists. Here each polygon of the reciprocal diagram corresponds to a vertex in the graph of the packing above it, and corresponding edges are perpendicular. If there isa rigid ordering and a reciprocal stress diagram, the ordering is also indicated in the stress diagram. Stress diagrams are discussed in section VII of part I [4, p.521. By a theorem of Roth and Whiteley [8] (see theorem 6.1 of part I [4]), we know that the framework of a packing G,(p) has both the associated rod framework G,(p) infinitesimally rigid and a reciprocal stress diagram if and only if G,(p) is infinitesimally rigid. Thus if there is a rigid ordering and the stress exists for arbitrarily large subpackings, then we know that the packing is finitely stable. If there is no rigid ordering, G,(p) may still be infinitesimally rigid, but for each of our cases, when there is no rigid ordering, G,(p) will IV LES 31 NPES RE JUXTAPOSlTlOlys RE CERCLES Dans ce qui suit, on verra des representants des 31 types de juxtapositions regulieres connexes de cercles dans le plan. IIs sont extraits du livre de L. Fejes Toth [6] ; on a toutefois choisi un ordre different, de telle sorte que les juxtapositions apparentees soient proches les unes des autres. On peut consulter aussi Griinbaum & Shephard [7] pour une description de la classification. Dans chaque diagramme (figure 4, pages 66 a 70), on montre tout d’abord la juxtaposition accornpagnee de I’indication de son graphe. Sur chaque diagramme, on a identifie un ordre rigide, si un tel ordre existe, en supposant que les sommets de la frontiere sont fixes. En effet, en ajoutant les sommets de la charpente de barres associbe aux sommets fixes dans I’ordre indique, on obtiendra successivement des charpentes infinitesimalement rigides. Chaque nouveau sommet doit &re lie a au moins deux sommets deja existants de telle maniere qu’ils ne soient pas tous les trois colineaires. Voir le lemme 6.2 de la partie I [4, p.521. Directement adroite de chacune des 31 juxtapositions, on a indiqub un diagramme rbciproque, s’il en existe. Ici, chaque polygone du diagramme reciproque correspond a un sommet dans le graphe de la juxtaposition qui se situe a cBte de Iui, et les aretes correspondantes sont perpendiculaires. Si un ordre rigide et un diagramme reciproque de contrainte existent, I’ordre est aussi indique dans le diagramme de contrainte. Les diagrammes de contrainte sont traites dans la section VII de la partie l [4, p.521. Selon un theoreme de Roth et Whiteley [8] (voir le theoreme 6.1 de la partie I [4]), on sait que la charpente d’une juxtaposition Gp(p) possede a la fois une charpente de barres associee c,(p) infinitesimalement rigide et un diagramme de contrainte reciproque si et seulement si G,(p) est infinitesimalement rigide. Ainsi, s’il y a un ordre rigide et que la contrainte existe pour des sous-juxtapositions 64 not be infinitesimally rigid. Here of course all but afinite number of the vertices are fixed. Similarly, for the cases of those packings (1 to 16, Figure 4) where no reciprocal stress diagram is given, we will show that it in fact does not exist. Thus by Roth and Whiteley in either case, some Cp(p) is not infinitesimally rigid or the stress diagram does not exist, P is not finitely stable. For packings 17 and 18 (Figure 4) we will show directly that cp(p) is not infinitesimally rigid by exhibiting a non-trivial infinitesimal flex p’. In case the degree of each vertex of G,is 3, we know from Theorem 3.1 that if we take any cycle in Gpthen the framework with just that cycle as the variable vertices is not infinitesimally rigid. Thus P is never finitely stable in case each circle touches just 3 others, since thereisalwaysacycleinsuchgraphs.Thisshowspackings19to31 (Figure 4) are not finitely stable. In case each of the regions defined by G,(p) is a regular polygon, a reciprocal diagram always exists by joining the centers of adjacent regular polygons. In the diagram we have chosen the most “regular” reciprocal, although any representative would do. In each of the cases when a reciprocal exists we expect that the general construction should be clear. In the cases when the reciprocal does not exist, we leave that part of the picture blank. In all of the cases (although it does not seem to follow from a general theorem) it turns out that if a reciprocal exists for every finite portion of the packing, an infinite reciprocal diagram exists for the whole packing. We have chosen to show this diagram, even if each finite diagram could be made more regular. arbitrairement grandes, alors on sait que la juxtaposition est de stabilite finie. S’il n’y a pas d’ordre rigide, cp(p) peut encore &re infinitesimalement rigide; mais pour les cas consideres ici, lorsqu’il n’y aura pas d’ordre rigide, Gp(p) ne sera pas infinitesimalement rigide. Ici, evidemment, tous les sommets sauf un nombre fini sont fixes. De mime, en ce qui concerne les cas des juxtapositions 1 a 16 (figure 4) pour lesquelles on ne donne pas de diagramme de contrainte reciproque, on montrera qu’en fait il n’en n’existe pas. Ainsi, par Roth et Whiteley dans les deux cas, que ce soit parce que G,(p) n’est pas infinitesimalement rigide ou parce qu’il n’existe pas de diagramme de contrainte, P n’est pas de stabilite finie. Pour les juxtapositions 17 et 18 (figure 4), on montrera directement que Gp(p) n’est pas infinitesimalement rigide en exhibant une deformation infinitesimale non triviale p’. Si le degre de chaque sommet de Gp est egal a 3, on sait par le theoreme 3.1 que pour tout cycle dans G,, la charpente n’ayant que les sommets de ce cycle comme sommets variables n’est pas infinitesimalement rigide. Ainsi, P n’est pas de stabilite finie si chaque cercle n’en touche que 3 autres, puisqu’il y a toujours un cycle dans de tels graphes. Ceci demontre que les juxtapositions 19 a 31 (figure 4) ne sont pas de stabilite finie. Si chacune des regions definies par G,(p) est un polygone regulier, il existe toujours un diagramme reciproque construit en joignant les centres des polygones reguliers adjacents. Dans le diagramme, on a choisi la reciproque la plus (( reguliere )), meme si tout representant aurait fait I’affaire. Dans chacun des cas 00 une reciproque existe, on espere que la construction generale est Claire. Lorsqu’il n’existait pas de reciproque, on a laisse en blanc cette partie de la figure. Dans tous les cas, (mime si ce ne semble pas decouler d’un theoreme general) il apparait que si une reciproque existe pour toute partie finie de la juxtaposition, il existe un 65 FIGURE 4 Pages 66 to 70. Drawings/Dessins: Richard Geoffrion. TABLE 1 / TABLEAU 1 The information is summarized in Table 1, where we have also included the information about whether the packing is 1-stable. Of course, many of the packings indicated by the pictures are just one packing in a family of packings, but it happens to turn out that for each case, for finite stability, if one of these packings is finitely stable, all members are. If a given family of packings is not finitely stable, we indicate an integer n, where the packings are not n-stable. However, for three families of packings 13, 14, and 16, such an n depends on which member of the family is being considered, and as a certain parameterchanges, thisn can bearbitrarilylarge. 1.e.theyarethe"bombs" as mentioned in the introduction. This is indicated by 00 in the table. For the case of 1-stability we indicate by an 'S'the situation where some of the packings in the given family are 1-stable, and some are not 1 -stable. For the whole table, 'A indicates that the condition always holds, and 'N' indicates that it never holds. diagramme reciproque infini pour la juxtaposition en entier. Les choixont ete realises en fonction de ce diagramme, m6me si chaque diagramme fini aurait pu &re plus rkgulier. Le tableau 1 contient un resume de cette information ; on y indique aussi si la juxtaposition est 1-stable. Evidernment, plusieurs juxtapositions illustrees ne sont qu'une juxtaposition parrni une famille de juxtapositions ; mais il apparait que dans chacun de ces cas, en ce qui concerne la stabilite finie, si I'une des juxtapositions d'une famille possede cette propriete, tous les membres de cette famille la possedent. Lorsqu'une certaine famille de juxtapositions n'est pas de stabilite finie, on I'indique par un entier n tel que les juxtapositions de cette farnille ne sont pas n-stables. Toutefois, pour trois familles de juxtapositions, celles qui portent les numeros 13, 14 et 16, un tel n depend du membre de la famille considere, et selon les variations d'un certain parametre, ce n peut itre arbitrairernent grand. II s'agit des (( bombes )) mentionnees dans I'introduction. Dans le tableau, on indique par 00 une telle situation. Pour ce qui est de la 1-stabilite, un 'S' indique que ceflaines juxtapositions de la famille en question sont 1 -stable, et certaines ne le sont pas. Pour I'ensemble du tableau, 'A indique que la propriete est toujours valide, et 'N' indique qu'elle ne I'est jamais. Rod framework is infinitesimally rigid Rigiditk infinitksimale / charpente de barres AAAAAAAAAAAAAAAANNNNNNNNNNNNNNW Reciprocal exists Existence de la rkciproque Packing is finitely stable Stabilitb finie de la juxtaDosition Packing Is 1-stable 1-stabilit.4 de la juxtaposition AAAAAAAAAAAANNAAANAAANNAANNAANN A A A A A A A A A A A A NNA NN18 Nl8 N6 N6 N6 N6 N6 N4 N4 N4 N4 N4 N3 N3 N3 AAAAAAAAAAAAAAAAAAAAAAAAAASAASS 72 FIGURE 7 Decompose the lines of the reciprocal into two overlapping hexagonal "tilings" as in Figure 7. The only requirement for the reciprocal is that the two hexagonal tilings overlap at the indicated vertices and that the angles for each tiling, separately at evety pair of intersecting edges, be 120". The \ / I two tilings will be tilted (for packing number 16) at some angle 9 < 60". Of course, the hexagonal tiles need not be regular. We now look at one hexagonal tile with the lengths of the sides as indicated in Figure 8. The dotted lines (.....) are parallel to the corresponding broken lines (-----) of the hexagonal tiling, and are there for reference. FIGURE a w5 Lemma 5.1 w,/w, 1 k, > 1 and 03/01 5 k, > 0, where k, and k, I ; are functions of 9 only. - - - - - - - - - - -.- - I '\: '. Proof For w1/w4 , look at Figure 9 near the 0 vertex. . c.. . ...I.... (60'-2 .. .. {/ ; By the law of sines I . \ \ \ Let k, = (-) sin 120" = (-) sin 60" > sin 9 sin 8 -- It is clear that w, > w, , o4 > a,. Thus On decompose les segments de droite de la reciproque en deux (( pavages )) hexagonaux se chevauchant, comme A la figure 7. Les seules exigences pour la reciproque est que les deux pavages hexagonaux se chevauchent aux sommets indiques et que, pour chaque pavage separement, I'angle en toute paire d'ar4tes se coupant soient de 120". Pour la juxtaposition 16, les deux juxtapositions basculeront a un certain angle 9 < 60". Evidemment, les paves hexagonaux ne sont pas necessairement reguliers. Considerons un pave hexagonal de cBtes de longueurs telles qu'indiqueesa la figure 8. Les lignes pointillees (..-.) sont parallbles aux lignes brisees (-----) correspondantes dans le pavage hexagonal ; on les indique a titre de reference. Lemme 5.1 a,/w, 2 k, > 1 et 03/w1 5 k, > 0, 00 k, et k, sont fonctions de 9 uniguernent. Dhonsfrafion Pour w,/w, , on examine la figure 9 pres du sommet 0. Par la Ioi des sinus - - x- -~ 01 -=- X 04 sin 9 sin 120" ' sin 120" sin 9 w,=x- - sin 120" - sin 120" sin 9 Soit k, = (-) sin 120" = (-) sin 60" > sin 8 sin 8 - =k,>l. w4 04 -- II est clair que a, > o, , o, > a,. Ainsi - - >3 = k, >l. 04 04 73 FIGURE g / / 120" ** ........... .- 120" ,120" To get the other inequality look at the lower right hand quadrilateral (Flgure 10). - 03 = X sin 120" sin(60 -0) sin 120" sin (60"- 0) 03 < a, = x =a, - ... sin 9 sin 120" sin 120" sin 120" sin(60"- 0) < sin(60"-0) 0 Let k2 = sin ; then 3 I k, , sin (60"- 9) 01 We continue to look for a contradiction. From Figure 8 we can shift the indices by 2 and apply Lemma 5.1 in each case. We get 03/o, I k*, 05/03 I k,, w1/w5 I k, 04/w1 I Ilk, < 1, os/03 I llk, < 1, 02/05 I Ilk, < 1 , Combining we get For the final contradiction, suppose we have a chain of hexagons as above, but satisfying the above inequalities on their edge lengths. Note that the directions of increasing and decreasing lengths are alwaysthesame,and inoursituation theyareasfollowsin Figurell. Thus one can find arbitrarily long chains of hexagons in the shape of a closed triangle with only 3 changes in direction, as in Figure 12. Afin d'obtenir I'autre inegalite, on observe le quadrilatere se trouvant en bas eta droite (figure 10). - 03 = X sin 120" sin(60 - 0) sin 120" o3 < G3 = x sin(60"- 0) - sin 9 sin 120" sin 120" - - 0,. ~. < sin(60"- 0) sin 120" sin (60"- 0) 0 Soit k2 = Sin ' ; alors 3 I k, sin(60"- 9) 01 On cherche toujours une contradiction. On peut, dans la figure 8, deplacer de 2 les indices et appliquer le lemme 5.1 dans chaque cas. On obtient 03/01 I k, , 05/03 I k, , w1/05 I k, 04/w1 I l/k, < 1, 06/W3 I l/k, < 1, o*/w5 I l/k, < 1 . En combinant ces resultats. on obtient Afin d'obtenir la contradiction finale, on suppose que I'on a une chaine d'hexagones comme ci-dews et dont les longueurs d'argtes satisfont les inegalites precedentes. On note que les directions de croissance et de decroissance des longueurs sont toujours les m&nes et, dans la situation qui nous occupe, elles sont telles que presentees dans la figure 11. Ainsi, il est possible de trouver des chaines d'hexagones arbitrairement longues qui se presentent sous la forme d'un triangle ferme possedant seulement 3 changements de direction (figure 12). 74 FIGURE 12 Suppose one proceeds n steps on each side of the triangle of hexagons. If we label the lengths of the sides indicated by !, , . . ., esn, then But this is impossible since k, > 1, if n is chosen large enough. Thus packing number 16 has no reciprocal diagram if the number of packing elements for which it corresponds is large enough. Thus packing 16 is not finitely stable. Packings 17and 18 For both packings G,(p) is not infinitesimally rigid. We indicate the infinitesimal motion in Figure 13. Only the 18 vertices of the two inner rings move. For packing 18 there is no reciprocal diagram either, if one takes a large enough portion of the packing. As in cases of packings 13,14 and 16 as the rhombus becomes more square, larger parts of the packing have a reciprocal diagram. Packing 4 In accordance with our policy of choosing the most regular reciprocal possible, we have chosen a tiling by congruent polygons. See the articles of D. Schattschneider [9] or J.A. Dunn [5]. Given our extra conditions and that the tiling is to be with congruent tiles, we are forced to choose the tiling shown. Packings 2,3,5 and 6 give other well-known tilings by congruent pentagons. Packings 18,22,23,26,30 and 31 For these packings there is no reciprocal diagram, but this is not needed to show that they are not finitely stable. Special arguments (which are omitted) handle each of these cases. Supposons que I’on effectue n etapes sur chaque cote du triangle d’hexagones. Si on etiquette les longueurs desardtes par t, ,. . ., la”, alors Mais ceci est impossible puisque, si n a ete choisi suffisamment grand, k, > 1. Ainsi, la juxtaposition numero 16 ne possede pas de diagramme reciproque si le nombre d’elements de juxtaposition qui lui correspond est suffisamment grand. La juxtaposition 16 n’est donc pas de stabilite finie. Juxtapositions 17 et 18 Pour ces deux juxtapositions, G,(p) n’est pas infinitesimalement rigide. La figure 13 illustre le mouvement infinitesimal. Ce ne sont que les 18 sommets des deux anneaux interieurs qui se deplacent. De plus, la juxtaposition 18 ne possede pas de diagramme reciproque lorsqu’on choisit une partie suffisamment grande de la juxtaposition. Comme dans les cas des juxtapositions 13,14 et 16, lorsque les losanges deviennent plus carres, de plus grandes parties de la juxtaposition possedent un diagramme reciproque. Juxtaposition 4 En accord avec le principe du choix de la reciproque la plus reguliere, on a choisi un pavage constitue de polygones congruents. On peut consulter a ce sujet les articles de D. Schattschneider [9] ou J.A. Dunn [5]. Etant donne les conditions supplementaires qu’on impose et le fait que le pavage doit dtre constitue de paves congruents, le pavage illustre est le seul choix. Les juxtapositions 2,3, 5 et 6 presentent d’autres pavages bien connus, constitues ceux-la de pentagones congruents. 75 Packinos 13, 14 and 16 There are the “bombs” mentioned in the introduction. These families of packings have as limits packing 8, for packings 13 and 14; and packing 15,forpacking 16.The limit packings havea reciprocal, and cp(p) is infinitesimally rigid forthe limit packings (whereall but a finite number of the vertices are fixed). For a fixed finite portion of G,, there are a finite number of inequalities that determine the infinitesimal rigidityof G, (p) (in afinitedimensional Euclidean space of infinitesimal deformations), as in section II (or section 111 of part I [4]). Then any sufficiently small perturbation of the inequalities does not create a non-zero solution. Thus as P approaches its limit, arbitrarily large sets of vertices must be allowed to be variable, in order for P not to be finitely stable. Thus since c,(p) is always infinitesimally rigid in these examples, the reciprocal diagram exists for arbitrarily large portions of G, (p), as P approaches its limit. .11111. Juxtapositions 18,22,23,26, 30 et 31 Ces juxtapositions ne possedent pas de diagrarnmes reciproques, mais il n’est pas necessaire de montrer qu’elles ne sont pas de stabilitefinie. On peut traiter chacun de ces cas a I’aide d’arguments particuliers (que I’on omettra). Juxtapositions 13, 14 et 16 Ce sont les (( bombes )) deja mentionnees en introduction. Ces familles de juxtapositions ont comme limites la juxtaposition 8, en ce qui concerne les juxtapositions 13 et 14; et la juxtaposition 15, pour la juxtaposition 16. Les juxtapositions limites possedent des reciproques, et G, (p) est infinitesimalement rigide pour les juxtapositions limites (oa tous les sommets sauf un nombre fini sont fixes). Pour une partiefinie fixee de G,, il existe un nombre fini d’inegalites qui determinent la rigidit6 infinithimale de Gp(p) (dans un espace euclidien de dimension fini de deformations infinitesimales), comme alasection II (ou lasection Ill de la partie I).Alors, toute perturbation suff isamment petite des inegalites n’entraine pas une solution non nulle. Ainsi, lorsque P s’approche de sa limite, des ensembles arbitrairement grands de sommets peuvent &re variable, afin que P ne soit pas de stabilite finie. Ainsi, puisque G,(p) est toujours infinitesimalement rigide dans ces exemples, le diagramme reciproque existe pour des parties arbitrairement grandes de G, (p), lorsque P tend vers sa limite. .11111. 76 BlBuoGRA PH Y [l] L. Asimow and B. Roth “Tha rlgldlty of graphs.” Trans. Arner. Math. SOC. 245 (1975), An introduction to the basic theory of p.279-289. rigidity. Une introduction B la theorie fondamentale de la rigidite. [2] L. Asimow and B. Roth “The rlgldlty of graphs 11.” J. Math. Appl. 68 (1979), p.171-190. A continuation of Part 1. La suite de la partie 1. [3] Robert Connelly “The rlgldlty of certain cabled frameworks and the second order rlgldlty of arbitrarily trlangulated convex suriacer.” Advances in Math. 37, N0.3 (1980), The title is the abstract. Le titre en est un resumd. p.272-299. [I] Robert Connelly “Rlgld circla and sphera packlngs. Part I: Flnlte packing%” Structural Topology, 14 (1988), p.43-60. The basic general theory used for the rigidity of packings. La thlorie generaale de base utilisee dans la rigidite des juxtapositions. [5] J.A. Dunn “Tessellations wlth pentqons.” Mathematical Gasette, 55, Dec. 1971, p.366-369. Follow-up correspondence Fxamples of tilings with pentagons. Fxemples de pavages d I‘aide de pentag ones. V01.56, p.332-335. [6] L. Fejes T6th Regular Flgum. Pergarnon Press (1964). An introduction to many ideas related to packing and covering problems. Une introduction B plusieurs idees Wes aux problimes de juxtaposition et de recouvrement. [7] Branko Grunbaum and G.C. Shephard “A hlerarchy of classlflcatlon mathods to patterns.” Zeitschrift fur Kristallographie, 154 A careful discussion of the method of classification of regular packings. Une discussion soignee de la methode de classification des juxtapositions reguli&res. (1 981 ), p.163-I 87. [8] B. Roth and W. Whiteley “lensegrity frameworks.” Trans. of A.M.S. (1981), p.410-446. The basics of statics and infinitesimal rigidity for frameworks with cables and struts. Les fondements de la rigiditd statique et de la rigidite infinitesimaie des charpentes de cables et d’etais. [8] Doris Schattschneider “llllng the plane wlth congruent pentagons.” Math. Mag., Vo1.51, No.1, Jan.1978, p.2944. More examples of tilings of the plane with congruent pentagons. Encore des exemples de pavages du plan B I’aide de pentagones congruents.