Rube
Cunne//p
Depa men
o
Ma hema ics
Co nell Uni e si y
I haca,
N
Y
14853
Pa ially suppo ed by
N.S.F.
g an , numbe
MCS-
790251, as well as he
I.H.E.S.,
Bu es-su -Y e e,
F ance. Suppo was also gi en by he Uni e si y o
Dijon, Sa oie Uni e si y
in
F ance, and he Max-
Planck-Ins i u e u Ma hema ik a Bonn, Wes
Ge many.
Sub en ionnb, en pa ie, pa
le
N.S.F.
(nume o de
sub en ion MCS-790251), ainsi que pa
I'I.H.E.S.
a
Bu es-su -Y e e, F ance. L'uni e si k de Dijon
e
I'uni e si b Sa oie en F ance,
ie
Max-Planck-
Ins i u e u Ma hema ik
a
Bonn, en Allemagne de
I'Oues , on aussi appo e leu appui.
F ench
ansla ion:
T aduc ion
angaise
:
Jean-Luc Raymond
RIGID CIRCLE AND SPHERE
PA CKINGS
PART
11
:
INFINITE PACKINGS
WITH FINITE MOTION
ABSTRACT
A packing Po ci cles in he plane is called n-s able, o
n
=
1,2,.
. .
i e e y se o n ci cles
is
held ixed by he es .
P
is called ini ely
s able i
i
is n-s able o e e y
n
=
1,
2,.
.
.
Fo each o he
31
ami-
lies o egula connec ed ci cle packings in he plane we classi y
which a e ini ely s able and which a e no . Fo
3
o he cases when
he amilies o packings a e no ini ely s able, i u ns
ou
ha he
smalles
n
o which hey a e no n-s able ge s a bi a ily la ge,
depending on a pa ame e o he amily.
I
INTRDDUCTION
Suppose we ha e a packing o ci cles in he plane.
How
should we
de ine wha i means o he packing
o
be s able? How do we
calcula e when his happens?
One eason o such ques ions is he main esul o pa
I
[4].
Roughly,
i
says ha locally maximally dense packings ha e igid
subpackings. Ano he eason is ha solid c ys al s uc u es mus
ha e some
so
o igidi y in o de o be s able unde ex e nal
pe u ba ions.
JUXTAPOSITIONS RIGIDES RE
CERCLES ET DE SPH€RES
PARTIE
11
:
JUXTAPOSITIONS INFINIES
DE
MOUVEMENT FIN1
Une jux aposi ion
P
de ce cles dans le plan es di e n-s able pou
n
=
1,2,
.
.
.
si
ou
ensemble de
n
ce cles es enu ixe pa les au es.
Pes des abili h inie si elle es n-s able pou
ou
n
=
1,2,
.
. .
Pa mi
les 31 amilles de jux aposi ions egulie es connexes de ce cles
dans le plan que I'on a classi iees, ce aines
son
de s abili e inie,
d'au es non. Dans
3
des cas de amilles de judaposi ions qui ne
son pas de s abili e inie, il appa ai que la plus pe i e aleu de
n
pou laquelle elles ne son pas n-s ables es a bi ai emen g ande,
e
depend d'un pa ame e de la amille.
I
INTRODUCTION
Conside ons une jux aposi ion de ce cles dans
le
plan. Comme
peu -on de ini ce que ep esen e la s abili e pou la jux aposi ion?
Commen peu -on calcule les cas
00
cela se p esen e?
Une des aisons de elles ques ions se si ue dans
le
esul a
p incipal de la pa ie
I
[4].
En g os, on y a i me que les jux apo-
si ions localemen maximalemen denses posseden des
sous-
jux aposi ions igides. Une au e aison es que les s uc u es d?
58
$?
FIGURE
1
L.
Fejes To h has al eady de ined a ci cle packing
o
be s able i
each ci cle is ixed by i s neighbo s. This is pa icula ly easy o
calcula e, bu
in
many cases i happens ha a packing is s able in his
sense,
bu
i e en jus h ee ci cles a e allowed o mo e, he packing
will “ allapa ”. Fo example, he ollowing packing,
Figu el,
has his
p ope y.
So
ins ead we choose a de ini ion o s abili y which we belie e
o
be
mo e ele an . We say a ci cle packing
P,
in he plane,
is
n-s able
i
e e y se o
n
ci cles, in
P,
is held ixed by he es o
P.
We say
P
is
ini ely s able
i
P
is n-s able o all
n
=
1,
2,
.
,
.
Thus
L.
Fejes To h’s
de ini ion o s abili y is wha we call 1-s abili y.
X
The main objec o
pa
II
is
o
classi y, among he 31 ypes o con-
nec ed egula packings
in
he plane, which a e ini ely s able and
which a e
no .
This is summa ized in
Table
1
(page 65). One eason
o choosing hese packings is ha since hey a e egula , hey a e
a po en ial sou ce o c ys al s uc u es. A packing is
egula
i he e
is a cong uence
o
he plane, aking he packing ci cles o packing
ci cles, ha akes any gi en ci cle o any o he .
U
Ano he eason o choosing hese packings is ha hey a easou ce
o in e es ing examples. In pa icula , packings numbe ed 13, 14,
and 15 ha e he p ope y ha hey can be hough o as
a
kind o
“bomb’:
In
each o hese examples he e is a pa ame e
€I
>
0
ha
desc ibes a packing
P,.
Then he e is an in ege
n(e)
>
0
such ha
P,
is n(e)-s able bu
no
n(e)+l-s able. Howe e , lim
n(8)
=
m.
I we choose
8
close
o
0,
we can imagine mo e and mo e ci cles
being allowed o mo e un il suddenly he whole packing collapses.
e+o
Basic o he analysis is he idea o a amewo k and he no ion
o igidi y and in ini esimal igidi y as discussed in pa
I.
To any
packing
P
we associa e a g aph
Gp
consis ing o a e ex co e-
sponding
o
each ci cle and an edge co esponding
o
each pai o
c is al solide doi en possede un ce ain ype de igidi e a in de
demeu e s ables
sous
les pe u ba ions ex e nes.
L.
FejesTo h adejade ini une jux aposi ion s able de ce cles comme
une jux aposi ion don chacun des ce cles es ixe pa ses oisins.
C’es pa iculie emen simple a calcule mais, dans plusieu s cas, il
appa ai qu’une jux aposi ion s able selon son sens, pou laquelle
on ne pe me qu’a ois ce cles de se deplace , se
((
desag ege a..
A
i e d’exemple, la jux aposi ion de la
igu e
1
possede ce e p o-
p ie e.
Ainsi, on adop e a plu B une de ini ion de s abili e qu’on c oi & e
plus app op iee. On di a qu’une jux aposi ion
P
de ce cles, dans le
plan, es
n-s able
si ou ensemble de
n
ce cles de Pes ixe pa le
es e de
P.
On di aque Pes de
s abili e inie
si Pes n-s able pou
ou
n
=
1,
2,.
.
.
Ainsi, la s abili e elle que de inie pa
L.
Fejes To h
co espond a ce qu’on appelle la 1-s abili k.
Le p incipal bu de la
pa ie
II
es I’iden i ica ion, pa mi les 31 ypes
de jux aposi ions connexes egulie es dans
le
plan, de celles qui
son de s abili e inie
e
de celles qui ne
le
son pas. Ceci es esume
dans le
ableau
1
(p. 65). Une aison qui jus i ie le choix de ces
jux aposi ions es que puisqu’elles son egulie es, elles cons i uen
une sou ce po en ielle de s uc u es c is allines. Une jux aposi ion
es
egulie e
s’il exi e une isome ie du plan, aisan co espond e
chaque ce cle de la jux aposi ion
a
un ce cle de la jux aposi ion, qui
en oie ou ce cle donne su n’impo e quel au e.
Une au e aison du choix de ces jux aposi ions es qu’elles son la
sou ce d’exemples in e essan s.
En
pa iculie , les jux aposi ions de
nume o
13,14
e 15 posseden la p op ie e de pou oi & e in e p e-
ees comme une so e de
((
bombe
)).
Dans chacun de ces exemples,
il exis e
un
pa ame e
0
>
0
qui ca ac e ise une jux aposi ion
Po.
II
exis e alo s un en ie
n(e)
>
0
el que
P,
es n(e)-s able mais n’es
pas n(e)+l -s able. Tou e ois, lim
n(e)
=
W.
e-+o
59
in e sec ing ci cles. The amewo k Gp(p) associa es e ex
i
o
pi,
he cen e o ci cle
i.
p
=
(pl,
.
.
.).
I
u ns
ou
ha he igidi y o
Gp(p)
is de e mined by i s in ini esimal igidi y, and hisallows
us
o
apply many known echniques.
Fo many o he
31
packings, a i s sigh , i does no seem ob ious
which a e ini elys ableand which a e no . 0ne’s”physical in ui ion”
can some imes be misleading. E en physical expe imen s ha e
o
be done ca e ully; he p ope y o he bombs migh be ha d o
de ec . We belie e ha he
ools
p esen ed he e and in pa
I
a e a
good i s s ep in unde s anding he igidi y o packings.
We hank B anko G unbaum o poin ing
ou
many mis akes and
making many commen s in an ea lie e sion o his pape .
I
CALCULA
TlONS
Suppose G(
p)
is a ini e amewo k in Euclidean space
Ed
as de-
sc ibed in pa
I,
[l]
o
[3],
bu wi h
k
ixed e ices,
n
-
k
a iable
e ices, and
e
membe s, all s u s.
p=
(pl,
. .
.,
p,)
is he sequence
o e ices o G(
p).
Tha is, all dis ances be ween s u endpoin s a e
no allowed
o
dec ease.
Suppose G(
p)
is in ini esimally igid. Since all membe s a e s u s,
his can only happen i he e a e su icien ly many ixed e ices
(a leas
d+l),
and he only i ial in ini esimal lexo
G(p)
is
p’=
0,
whe e
p’=
(p;,
...,
pi).
Thus
p’=
0
is he only solu ion
o
he ollowing sys em o inequali-
ies:
(p;-p;)-(p,-pj)
2
O, o li,jlamembe o
G.
This is a sys em o
e
linea inequali ies in
d(n-
k)
a iables, he
coo dina es o he a iable e ices. This has only he ze o solu ion
only i
d(n-k) l
I
e.
(2.1
1
Si on choisi
8
p es de
0,
on peu imagine que
de
plus en plus de
ce cles puissen se deplace jusqu’a
ce
que soudainemen la
jux aposi ion en ie e s’e ond e.
A
la base de ce e analyse, on ou e le concep
de
cha pen e e les
no ions de igidi e
e
de igidi e in ini esimale p esen es dans la
pa ie
I.
A
ou e jux aposi ion
P,
on associe un g aphe Gpen aisan
co espond e un somme a chaque ce cle e une a e e a chaque
pai e de ce cles d’in e sec ion non nulle. La cha pen e Gp(p) as-
socie
le
somme
i
a
p,,
le cen e du ce cle
i.
p
=
(pl,
. .
.).
II
appa aT
que la igidi e de Gp(p) es de e minee pa sa igidi e in ini esimale
e ceci pe me d’applique plusieu s echniques connues.
Plusieu s des
31
jux aposi ions ne semblen pas, a p emie e ue,
pou oi B e classi iees de aqon e iden e comme e an de s abili e
inie ou non. L’ccin ui ion physique)) peu pa ois indui e en e eu .
MBme les expe iences physiques doi en e e ealisees a ec p e-
cau ion; la p op ie e des bombes peu B e di icile a decele . Les
ou ils p esen es ici e dans la pa ie
I
appa aissen
a
I’au eu comme
un bon pas e s la comp ehension de la igidi e des jux aposi ions.
L’au eu eme cie B anko G unbaum pou a oi signale plusieu s
e eu s e a oi emis plusieu s commen ai es au suje d’une e sion
p eceden e de ce a icle.
I/
CALCULS
Supposons que G(
p)
soi une cha pen e inie dans I’espace eucli-
dien
Ed
elle qu’on I’a dec i e dans la pa ie
I,
dans
[l]
ou
dans
[3],
mais possedan
k
somme s ixes,
n
-
k
somme s a iables e
e
memb es, ousdese ais.
p=
(p,, ...,p,,)
es lasui edessomme s
de G(p). Ainsi, aucune dis ance en e les ex e ni es d’un e ai ne
peu dec oi e.
Supposons que G(
p)
soi in ini esimalemen ig ide. Puisque
ous
60
I
is help ul o ew i e
(2.1)
in e ms o he
a e age deg ee
o
a
e ex
7
whe e
-
i ,
V=C-
,
is he deg ee o he i- h a iable e ex in
G.
A e ex has
deg ee
i i is a e ex o exac ly
edges (also called membe s).
i
(n-k)
’
Suppose ha each ixed e exo
G
isonexac lyoneedgeo
G.
Then
he numbe o e ex-edge incidences is
2e
=
(C
,)
+
k,
whe e he sum is o e a iable e ices as be o e. Thus
2e
=
(n-
k)
V+
k.
(2.2)
Combining his wi h
(2.1)
we ge
d(n-k)+1
I
‘/Z[(n-k) +k],
2d-(%)s
V
La e in ou applica ions o packings
i
will u n ou ha
k
will be
much smalle han
n,
and
so
will hen be no much smalle han
2
d.
ses memb es son des e ais, ceci ne peu se p odui e que s’il y a un
nomb e su isammen g and de somme s ixes (au moins
d+l);
le
seul mou emen in ini esimal de
G(p)
es
p’=
0,oU
p‘=
(
p;,
. .
.,
p;).
Ainsi
p’=
0
es la seule solu ion du sys eme d’inequa ions sui an
:
(p;
-
pi).
(pi-
pj)
2
0,
pou
{i,
jl
memb e de
G.
C’es un sys eme de
e
inequa ions lineai es en
d(n-
k)
a iables,
les coo donnees des somme s a iables.
II
ne possede que la
solu-
ion nulle seulemen si
d(n-k) 1
2
e. (2.1
1
II
es u ile de eec i e
(2.1)
en onc ion du
deg 6 moyen d’un
som-
me
V,
oh
-
i ,
V=S-
I (n-k)
OD
,
es le deg e du i-e ne somme a iable de
G.
Un somme es
de
deg e
s’il es
le
somme d’exac emen
a e es (memb es).
Supposons que chaque somme ixe de
G
soi su exac emen une
a Q e de
G.
Alo s le nomb e d’incidences somme -a 8 e es
2e
=
(C
i)+k,
OD
la somme pa cou les somme s a iables comme p ecedem-
men . Ainsi
2e
=
(n-
k)
V+
k.
(2.2)
En combinan ce esul a a ec
(2.1),
on ob ien
d(n-k)+l
2
Vz[(n-k)V+k],
2d-(S)s
V
(2.3)
Plus
loin dans les applica ions aux jux aposi ions,
il
appa ai a que
k
es beaucoup plus pe i que
n,
e
ainsi ne se a pas beaucoup
plus pe i que
2d.
61
Ill
GRAM WITHSM AVERAGE DEGREE
We can use he calcula ions o sec ion
II
o
elimina e as being igid
many g aphs wi h low a e age deg ee
7.
Theo em
3.7
Le
G(p)
be a connec ed (in ini esimal&) igid s u
g aph in
Ed
whe e each a iable e ex
o
G
has deg ee
d
+
1,
and
each ixed e ex has deg ee
1.
Then
G
is a ee. 1.e. he e a e no
cycles in
G.
P oo Using he no a ion abo e,
7
=
d+l.
Then
(2.2)
implies,
2(n-
e)
=
2n- (n-
k)
(d
1)
-
k
=
2n- (n-
k)
d-n+
k- k
(3.1
1
=
n-(n-k)d.
On he o he hand, since
G(
p)
is igid, using
(2.3)
and
7
=
d
1,
we
ge
2d-
(x)
k-
2
2
d+l
,
which simpli ies o
2
I
n-d(n-k).
Combining
(3.1)
and
(3.2)
we ge
2
I
2(n-e)
o
1
5
n-e.
Since
G
is
connec ed, his implies
G
is a ee.
111
GRAPHES
DE
PETIT
DEGREMOYEAT
En u ilisan les calculs de la sec ion
II,
il
es passible d’elimine
plusieu s g aphes de pe i deg e moyen
7,
ceux-ci e an igides.
Theo 4me
3.7
Soi
G( p)
un g aphe d’e ais connexe (in ini hima-
lemen ) igide dans
Ed,
00
chaque somme a iable de
G
es de deg e
d
+
1
e chaque somme ixe es de deg 6
1.
Alon
G
es un a b e.
C’es -a-di e qu’il n’y a aucun cycle dans
G.
Ddmons a ion
A ec la no a ion in odui e p ecedemmen , on
a
= d
+
1.
Alo s,
(2.2)
implique
-
2(n-
e)
=
2n- (n-
k)
(d
1)
-
k
=
2n- (n-
k)
d- n+
k-
k
=
n-(n-k)d.
(3.1)
D’au e pa , puisque
G(p)
es igide, en in oquan
(2.3)
e le ai
que
7
=
d +1,
on ob ien
ce qu’on peu simpli ie de la acon sui an e:
2
I
n-d(n-k).
En combinan
(3.1)
e
(3.2),
on ob ien
2
5
2(n-e)
ou
1
I
n-e.
Puisque
G
es connexe, ceci implique que
G
es un a b e.
(3.2)

62
FIGURE
2
In he plane
E2
his says ha i he deg ee o each a iable e ex
is 3, hen he e can be no cycles i
G(p)
is
o
be igid. Fo example,
he s u amewo k (Figu e
2)
is no igid. Va iable e ices a e
deno ed by
0,
ixed e ices by
0,
and
ep esen a s u .
No e ha in he abo e, he e is no eal
loss
o gene ali y in assuming
ha he deg ee o each ixed e ex is
1.
We can c ea e a ixed e ex
o each edge ha has some ixed e ex on i and ega d each o
hese new ixed e ices as dis inc in
G
bu wi h he same posi ion
ec o s
pi
in he amewo k
G(p).
o
FIGURE
3
Al e na i ely, suppose
i
is a ixed e ex o
G,
j
is a a iable e ex,
and
(i,
j}
is an edge o
G.
Then we can eplace
Ii,
11
wi h
Ii:
j}
whe e
i’
is ano he ixed e ex and pu
p,.
anywhe e on he ay om
p,
o
pi
in
Ed,
o
ge a new g aph and a new amewo k ha is in ini esi-
mally igid i and only i he o iginal g aph
G(p)
is. See Figu e
3.
Y
w
wi h
es
is
eplaced e nplack
JI
We can do he abo e p ocess o each
Ii,
jl
membe in
G
o all
j
and
hen elimina e
i.
The e is also a con e se
o
Theo em 3.1. Namely i each a iable
e exo
G(p)
isin he in e io o hecon exhullo i sd l neighbo s,
he endpoin s o
G
a e he ixed e ices, and
G
is a ee, hen
G(p)
is in ini esimally igid. We omi he p oo .
Dans
le
plan
E2,
ce esul a a i me que
si
le
deg e de chaque som-
me a iable es egal
a
3, alo s il ne peu y a oi aucun cycle si
G(p)
doi i e igide. Pa exemple, la cha pen e d’e ais de laligu e
2
n’es
pas igide. Les somme s a iables son designes pa
0,
les
som-
me s ixes pa .,
e
ou
I
ep esen e un e ai.
On no e que dans ce qui p edde, il n’y a pas de e i able pe e de
gene ali i en supposan que
le
deg e de chaque somme ixe es
egal
a
1. On peu c ee un somme ixe pou chaquea h e possedan
au moins un somme ixe
e
in e p e e chacun de ces nou eaux
somme s ixes comme des somme s dis inc s dans
G
en conse -
an ou e ois les mhmes ec eu s de posi ion
pi
dans la cha pen e
G(
P)-
Comme al e na i e, supposons que
i
soi un somme ixe de
G,
j
un
somme a iable e
Ii,jl
une a h e de
G.
On peu alo s emplace
{iJ
pa
(i;j},
oh
i’es un au e somme ixe
e
pi.
es place n’impo e
oh
su le ayon qui a de
p,
a
pi
dans
Ed.
On ob ien un nou eau
g aphe
e
une nou elle cha pen e qui es in ini esimalemen igide si
e
seulemen si le g aphe o iginal
G(p)
I’es aussi. Voi la igu e
3.
Ce
p ocessus peu & e e ec ue su chaque memb e
(i,
jl
de
G
pou
ou
j
e
on elimine ainsi
i.
II
exis e une ecip oque au heo eme 3.1, En e e , si chaque som-
me a iable de
G(p)
se si ue
a
I’in e ieu de I’en eloppe con exe de
ses
d+l
oisins, que les ex emi es de
G
son les somme s ixes e
que
G
es un a b e, alo s
G(p)
es in ini esimalemen igide. On
ome a la demons a ion.
63
IV
THE 31 TYPES
OF
CIRCLE
PACKINGS
In he ollowing we shall show ep esen a i es o he 31 ypes
o
egula connec ed ci cle packings in he plane. These a e aken om
he booko
L.
FejesTo h [6], bu we ha echosenadi e en o de ing
so
ha ela ed packings a e nea o each o he . See also G iinbaum
and Shepha d [7] o a desc ip ion o he classi ica ion.
In each diag am
(Figu e
4,
pages 66-70) we i s show he packing
wi h he g aph
o
he packing indica ed as well. On his diag am we
ha e indica ed a igid o de ing, i
i
exis s, assuming he bounda y
e ices a e ixed. Tha is, by adding in he e ices o he associa ed
od amewo k
o
he ixed e ices in he o de indica ed, we ge
successi ely amewo ks ha a e in ini esimally igid. Each o he
new e ices
mus
be joined o a leas wo p e ious e ices such
ha all h ee do no lie on a s aigh line. See Lemma 6.2 o pa
I
[4, p.51
I.
Di ec ly beside each o he 31 packings, we ha e indica ed a ecip-
ocal diag am,
i
i
exis s.
He e each polygon o he ecip ocal dia-
g am co esponds o a e ex in he g aph
o
he packing abo e i ,
and co esponding edges a e pe pendicula . I he e isa igid o de -
ing and a ecip ocal s ess diag am, he o de ing is also indica ed in
he s ess diag am. S ess diag ams a e discussed in sec ion VII o
pa
I
[4, p.521.
By a heo em o Ro h and Whi eley
[8]
(see heo em 6.1 o pa
I
[4]), we know ha he amewo k o a packing
G,(p)
has bo h he
associa ed od amewo k
G,(p)
in ini esimally igid and a ecip o-
cal s ess diag am i and only i
G,(p)
is in ini esimally igid. Thus i
he e is a igid o de ing and he s ess exis s o a bi a ily la ge
subpackings, hen we know ha he packing is ini ely s able.
I he e is no igid o de ing,
G,(p)
may s ill be in ini esimally igid,
bu o each o ou cases, when he e is no igid o de ing,
G,(p)
will
IV
LES
31 NPES
RE
JUXTAPOSlTlOlys
RE
CERCLES
Dans ce qui sui , on e a des ep esen an s des 31 ypes de
jux aposi ions egulie es connexes de ce cles dans le plan.
IIs
son
ex ai s du li e de L. Fejes To h [6]
;
on a ou e ois choisi un o d e
di e en , de elle so e que les jux aposi ions appa en ees soien
p oches les unes des au es. On peu consul e aussi G iinbaum
&
Shepha d [7] pou une desc ip ion de la classi ica ion.
Dans chaque diag amme
( igu e
4,
pages 66
a
70),
on mon e
ou
d’abo d la jux aposi ion acco npagnee de I’indica ion de son g aphe.
Su chaque diag amme, on a iden i ie un o d e igide, si un
el
o d e
exis e, en supposan que les somme s de la on ie e son ixes. En
e e , en ajou an les somme s de la cha pen e
de
ba es associbe
aux somme s ixes dans I’o d e indique, on ob iend a successi e-
men des cha pen es in ini esimalemen igides. Chaque nou eau
somme doi & e lie
a
au moins deux somme s deja exis an s de
elle manie e qu’ils ne soien pas
ous
les ois colineai es. Voi
le
lemme 6.2 de la pa ie
I
[4, p.521.
Di ec emen ad oi e de chacune des 31 jux aposi ions, on a indiqub
un diag amme bcip oque,
s’il
en
exis e.
Ici, chaque polygone du
diag amme ecip oque co espond
a
un
somme
dans le g aphe de
la jux aposi ion qui se si ue a cB e de Iui, e les a e es co espon-
dan es son pe pendiculai es. Si un o d e igide e un diag amme
ecip oque de con ain e exis en , I’o d e es aussi indique dans
le
diag amme de con ain e. Les diag ammes de con ain e son ai-
es dans la sec ion VII de la pa ie
l
[4,
p.521.
Selon un heo eme de Ro h
e
Whi eley
[8]
( oi le heo eme 6.1
de la pa ie
I
[4]), on sai que la cha pen e d’une jux aposi ion
Gp(p)
possede a la ois une cha pen e de ba es associee
c,(p)
in ini e-
simalemen igide e un diag amme de con ain e ecip oque si
e
seulemen si
G,(p)
es in ini esimalemen igide. Ainsi, s’il y a un
o d e igide
e
que la con ain e exis e pou des sous-jux aposi ions
64
no be in ini esimally igid. He e o cou se all bu a ini e numbe o
he e ices a e ixed.
Simila ly, o he cases o hose packings (1
o
16,
Figu e
4)
whe e
no ecip ocal s ess diag am is gi en, we will show ha
i
in ac
does no exis .
Thus
by Ro h and Whi eley in ei he case, some
Cp(p)
is no in i-
ni esimally igid o he s ess diag am does no exis ,
P
is no
ini ely s able.
Fo packings
17
and
18
(Figu e
4)
we will show di ec ly ha
cp(p)
is no in ini esimally igid by exhibi ing a non- i ial in ini esimal
lex
p’.
In case he deg ee o each e ex o G,is 3, we know om Theo em
3.1 ha i we ake any cycle in Gp hen he amewo k wi h jus ha
cycle as he a iable e ices is no in ini esimally igid. Thus
P
is
ne e ini ely s able in case each ci cle ouches jus 3 o he s, since
he eisalwaysacycleinsuchg aphs.Thisshowspackings19 o31
(Figu e
4)
a e no ini ely s able.
In case each o he egions de ined by
G,(p)
is a egula polygon, a
ecip ocal diag am always exis s by joining he cen e s o adjacen
egula polygons.
In he diag am we ha e chosen he mos “ egula ” ecip ocal, al-
hough any ep esen a i e would do. In each o he cases when a
ecip ocal exis s we expec ha he gene al cons uc ion should be
clea . In he cases when he ecip ocal does no exis , we lea e ha
pa o he pic u e blank. In all o he cases (al hough
i
does no
seem
o
ollow om a gene al heo em) i u ns ou ha i a ecip o-
cal exis s o e e y ini e po ion o he packing, an in ini e ecip ocal
diag am exis s o he whole packing. We ha e chosen o show his
diag am, e en i each ini e diag am could be made mo e egula .
a bi ai emen g andes, alo s on sai que la jux aposi ion es de
s abili e inie.
S’il n’y a pas d’o d e igide,
cp(p)
peu enco e & e in ini esimale-
men igide; mais pou les cas conside es ici, lo squ’il n’y au a pas
d’o d e igide, Gp(p) ne se a pas in ini esimalemen igide. Ici, e i-
demmen , ous les somme s sau un nomb e ini son ixes.
De mime, en ce qui conce ne les cas des jux aposi ions 1
a
16
( igu e
4)
pou lesquelles on ne donne pas de diag amme de con-
ain e ecip oque, on mon e a qu’en ai il n’en n’exis e pas.
Ainsi, pa Ro h e Whi eley dans les deux cas, que ce soi pa ce
que
G,(p)
n’es pas in ini esimalemen igide
ou
pa ce qu’il n’exis e
pas de diag amme de con ain e, P n’es pas de s abili e inie.
Pou les jux aposi ions 17 e 18
( igu e
4),
on mon e a di ec emen
que
Gp(p)
n’es pas in ini esimalemen igide en exhiban une de-
o ma ion in ini esimale non i iale
p’.
Si le deg e de chaque somme de
Gp
es egal
a
3,
on sai pa le
heo eme 3.1 que pou ou cycle dans
G,,
la cha pen e n’ayan que
les somme s de ce cycle comme somme s a iables n’es pas
in ini esimalemen igide. Ainsi,
P
n’es pas de s abili e inie si cha-
que ce cle n’en ouche que 3 au es, puisqu’il y a oujou s un cycle
dans de els g aphes. Ceci demon e que les jux aposi ions 19
a
31
( igu e
4)
ne son pas de s abili e inie.
Si chacune des egions de inies pa
G,(p)
es un polygone egulie ,
il
exis e oujou s un diag amme ecip oque cons ui en joignan les
cen es des polygones egulie s adjacen s.
Dans
le
diag amme, on a choisi la ecip oque la plus
((
egulie e
)),
meme si ou ep esen an au ai ai I’a ai e. Dans chacun des cas
00
une ecip oque exis e, on espe e que la cons uc ion gene ale es
Clai e. Lo squ’il n’exis ai pas de ecip oque,
on
a laisse en blanc
ce e pa ie de la igu e. Dans ous les cas, (mime si ce ne semble
pas decoule d’un heo eme gene al) il appa ai que si une ecip o-
que exis e pou ou e pa ie inie de la jux aposi ion,
il
exis e un
65
FIGURE
4
Pages
66
o
70.
D awings/Dessins: Richa d Geo ion.
TABLE
1
/
TABLEAU
1
The in o ma ion is summa ized in
Table
1,
whe e we ha e also in-
cluded he in o ma ion abou whe he he packing is 1-s able.
O cou se, many o he packings indica ed by he pic u es a e jus
one packing in a amily o packings, bu i happens o u n ou ha
o each case, o ini e s abili y, i one
o
hese packings is ini ely
s able, all membe s a e.
I a gi en amily o packings is no ini ely s able, we indica e an
in ege
n,
whe e he packings a e no n-s able. Howe e , o h ee
amilies
o
packings 13, 14, and 16, such an
n
depends on which
membe
o
he amily is being conside ed, and as a ce ain pa am-
e e changes, hisn can bea bi a ilyla ge. 1.e. heya e he"bombs"
as men ioned in he in oduc ion. This is indica ed by
00
in he able.
Fo he case o 1-s abili y we indica e by an 'S' he si ua ion whe e
some
o
he packings in he gi en amily a e 1-s able, and
some
a e
no
1
-s able.
Fo he whole able,
'A
indica es ha he condi ion always holds,
and
'N'
indica es ha i ne e holds.
diag amme ecip oque in ini pou la jux aposi ion en en ie . Les
choixon
e e
ealises en onc ion de ce diag amme, m6me si chaque
diag amme ini au ai pu & e plus kgulie .
Le
ableau
1
con ien un esume de ce e in o ma ion
;
on y indique
aussi si la jux aposi ion es 1-s able.
E ide nmen , plusieu s jux aposi ions illus ees ne son qu'une
jux aposi ion pa ni une amille de jux aposi ions
;
mais il appa ai
que dans chacun de ces cas, en ce qui conce ne la s abili e inie, si
I'une des jux aposi ions d'une amille possede ce e p op ie e,
ous
les memb es de ce e amille la posseden .
Lo squ'une ce aine amille de jux aposi ions n'es pas de s abili e
inie, on I'indique pa un en ie
n
el que les jux aposi ions de ce e
a nille ne son pas n-s ables. Tou e ois, pou ois amilles de
jux aposi ions, celles qui po en les nume os
13,
14
e
16, un el
n
depend du memb e de la amille conside e,
e
selon les a ia ions
d'un ce ain pa ame e, ce
n
peu i e a bi ai e nen g and.
II
s'agi
des
((
bombes
))
men ionnees dans I'in oduc ion. Dans le ableau,
on indique pa
00
une elle si ua ion.
Pou ce qui es de la 1-s abili e, un
'S'
indique que
ce laines
jux a-
posi ions de la amille en ques ion son 1 -s able, e
ce aines
ne le
son pas.
Pou I'ensemble du ableau,
'A
indique que la p op ie e es
oujou s
alide, e
'N'
indique qu'elle ne I'es jamais.
Rod amewo k is in ini esimally igid
Rigidi k in ini ksimale
/
cha pen e de ba es
AAAAAAAAAAAAAAAANNNNNNNNNNNNNNW
Recip ocal exis s
Exis ence de la kcip oque
Packing is ini ely s able
S abili b inie de la jux aDosi ion
Packing
Is
1-s able
1-s abili .4 de la jux aposi ion
AAAAAAAAAAAANNAAANAAANNAANNAANN
A A A A A A A A A A A A
N-
N-
A
N-
N18
Nl8
N6 N6 N6 N6 N6
N4
N4
N4
N4
N4 N3
N3
N3
AAAAAAAAAAAAAAAAAAAAAAAAAASAASS
72
FIGURE
7
Decompose he lines o he ecip ocal in o
wo
o e lapping hexago-
nal " ilings" as in Figu e
7.
The only equi emen
o
he ecip ocal is ha he wo hexagonal
ilings o e lap a he indica ed e ices and ha he angles o each
iling, sepa a ely a e e y pai o in e sec ing edges, be 120". The
/
I
wo
ilings will be il ed ( o packing numbe 16) a some angle
9
<
60".
O
cou se, he hexagonal iles need no be egula .
We now look a one hexagonal ile wi h he leng hs
o
he sides as
indica ed in Figu e
8.
The do ed lines
(.....)
a e pa allel o he
co esponding b oken lines
(-----)
o he hexagonal iling, and a e
he e o e e ence.
FIGURE
a
w5
Lemma
5.1
w,/w,
1
k,
>
1
and
03/01
5
k,
>
0,
whe e
k,
and
k,
I
;
a e
unc ions o
9
only.
- -
-
-
- -
- - -
-
-.-
-
I
' :
'.
P oo
Fo
w1/w4
,
look a Figu e
9
nea he
0
e ex.
.
c..
.
...I....
(60'-2
..
..
{/
;
By he law o sines
I
.
Le
k,
=
(-)
sin 120"
=
(-)
sin
60"
>
sin
9
sin
8
--
I
is clea ha w,
>
w,
,
o4
>
a,.
Thus
On decompose les segmen s de d oi e de la ecip oque en deux
((
pa ages
))
hexagonaux se che auchan , comme
A
la igu e
7.
Les seules exigences pou la ecip oque es que les deux pa ages
hexagonaux se che auchen aux somme s indiques
e
que, pou
chaque pa age sepa emen , I'angle en ou e pai e d'a 4 es se cou-
pan soien de 120". Pou la jux aposi ion 16, les deux jux aposi ions
bascule on
a
un ce ain angle
9
<
60".
E idemmen , les pa es
hexagonaux ne son pas necessai emen egulie s.
Conside ons un pa e hexagonal de cB es de longueu s elles
qu'indiqueesa la igu e
8.
Les lignes poin illees
(..-.)
son pa allbles
aux lignes b isees
(-----)
co espondan es dans le pa age hexa-
gonal
;
on les indique
a
i e de e e ence.
Lemme
5.1
a,/w,
2
k,
>
1
e
03/w1
5
k,
>
0,
00
k,
e
k,
son
onc ions
de
9
unigue nen .
Dhons a ion
Pou
w,/w,
,
on examine la igu e
9
p es du
somme
0.
Pa la Ioi des sinus
- -
x-
-~
01
-=-
X
04
sin
9
sin 120"
'
sin 120" sin
9
w,=x-
-
sin 120"
-
sin 120"
sin
9
Soi
k,
=
(-)
sin 120"
=
(-)
sin
60"
>
sin
8
sin
8
-
=k,>l.
w4
04
--
II
es clai que
a,
>
o,
,
o,
>
a,.
Ainsi
-
-
>3
=
k,
>l.
04
04

73
FIGURE
g
/
/
120"
**
...........
.-
120"
,120"
To ge he o he inequali y
look
a he lowe igh hand quad ila e al
(Flgu e 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
Le
k2
=
sin
;
hen
3
I
k,
,
sin (60"-
9)
01
We con inue
o
look
o a con adic ion. F om
Figu e
8
we can
shi
he indices by
2
and apply Lemma 5.1 in each case. We ge
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 ge
Fo
he inal con adic ion, suppose we ha e a chain o hexagons as
abo e, bu sa is ying he abo e inequali ies on hei edge leng hs.
No e
ha he di ec ions
o
inc easing and dec easing leng hs a e
always hesame,and inou si ua ion heya eas ollowsin
Figu ell.
Thus one can ind a bi a ily long chains o hexagons in he shape o
a closed iangle wi h only
3
changes in di ec ion, as in
Figu e 12.
A in d'ob eni I'au e inegali e, on obse e
le
quad ila e e se ou an
en bas e a d oi e
( igu e 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
Soi
k2
=
Sin
'
;
alo s
3
I
k,
sin(60"-
9)
01
On che che oujou s une con adic ion. On peu , dans la
igu e
8,
deplace de 2 les indices e applique le lemme 5.1 dans chaque cas.
On ob ien
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 combinan ces esul a s. on ob ien
A in d'ob eni la con adic ion inale, on suppose que I'on a une
chaine d'hexagones comme ci-dews
e
don les longueu s d'a g-
es sa is on les inegali es p eceden es. On no e que les di ec ions
de c oissance e de dec oissance des longueu s son oujou s
les
m&nes
e ,
dans la si ua ion qui nous occupe, elles son elles que
p esen ees dans la
igu e
11.
Ainsi, il es possible de ou e des chaines d'hexagones a bi ai-
emen longues qui se p esen en
sous
la o me d'un iangle e me
possedan seulemen
3
changemen s de di ec ion
( igu e 12).
74
FIGURE
12
Suppose one p oceeds
n
s eps on each side o he iangle o hexa-
gons.
I
we label he leng hs o he sides indica ed by
!,
,
.
.
.,
esn,
hen
Bu his is impossible since
k,
>
1, i
n
is chosen la ge enough. Thus
packing numbe 16 has no ecip ocal diag am i he numbe
o
packing elemen s o which i co esponds is la ge enough. Thus
packing 16 is no ini ely s able.
Packings 17and
18
Fo bo h packings
G,(p)
is no in ini esimally igid. We indica e he
in ini esimal mo ion in
Figu e
13.
Only he 18 e ices o he wo
inne ings mo e.
Fo packing 18 he e is no ecip ocal diag am ei he , i one akes a
la ge enough po ion o he packing. As in cases o packings 13,14
and 16 as he hombus becomes mo e squa e, la ge pa s o he
packing ha e a ecip ocal diag am.
Packing
4
In acco dance wi h ou policy o choosing he mos egula ecip o-
cal possible, we ha e chosen a iling by cong uen polygons. See he
a icles o D. Scha schneide
[9]
o J.A. Dunn [5]. Gi en ou ex a
condi ions and ha he iling is
o
be wi h cong uen iles, we a e
o ced
o
choose he iling shown. Packings 2,3,5 and
6
gi e o he
well-known ilings by cong uen pen agons.
Packings 18,22,23,26,30 and 31
Fo hese packings he e is no ecip ocal diag am, bu his is no
needed
o
show ha hey a e no ini ely s able. Special a gumen s
(which a e omi ed) handle each o hese cases.
Supposons que I’on e ec ue
n
e apes su chaque co e du iangle
d’hexagones. Si on e ique e les longueu s desa d es pa
,
,.
.
.,
la”,
alo s
Mais ceci es impossible puisque, si
n
a
e e
choisi su isammen
g and,
k,
>
1. Ainsi, la jux aposi ion nume o 16 ne possede pas de
diag amme ecip oque si le nomb e d’elemen s de jux aposi ion qui
lui co espond es su isammen g and. La jux aposi ion
16
n’es
donc pas de s abili e inie.
Jux aposi ions
17
e
18
Pou ces deux jux aposi ions,
G,(p)
n’es pas in ini esimalemen
igide. La
igu e
13
illus e
le
mou emen in ini esimal.
Ce
ne son
que les
18
somme s des deux anneaux in e ieu s qui se deplacen .
De plus, la jux aposi ion 18 ne possede pas de diag amme eci-
p oque lo squ’on choisi une pa ie su isammen g ande de la
jux aposi ion. Comme dans les cas des jux aposi ions 13,14
e
16,
lo sque les losanges de iennen plus ca es, de plus g andes pa -
ies de la jux aposi ion posseden un diag amme ecip oque.
Jux aposi ion
4
En acco d a ec le p incipe du choix de la ecip oque la plus egu-
lie e, on a choisi un pa age cons i ue de polygones cong uen s. On
peu consul e
a
ce suje les a icles de
D.
Scha schneide
[9]
ou
J.A.
Dunn [5]. E an donne les condi ions supplemen ai es qu’on
impose e
le
ai que le pa age doi d e cons i ue de pa es cong u-
en s, le pa age illus e es
le
seul choix. Les jux aposi ions 2,3,
5
e
6 p esen en d’au es pa ages bien connus, cons i ues ceux-la de
pen agones cong uen s.
75
Packinos 13,
14
and 16
The e a e he “bombs” men ioned in he in oduc ion. These ami-
lies o packings ha e as limi s packing
8,
o packings 13 and 14;
and packing 15, o packing 16.The limi packings ha ea ecip ocal,
and
cp(p)
is in ini esimally igid o he limi packings (whe eall bu
a ini e numbe o he e ices a e ixed). Fo a ixed ini e po ion o
G,,
he e a e a ini e numbe o inequali ies ha de e mine he
in ini esimal igidi yo
G,
(p)
(in a ini edimensional Euclidean space
o in ini esimal de o ma ions), as in sec ion
II
(o sec ion
111
o
pa
I
[4]).
Then any su icien ly small pe u ba ion o he inequali-
ies does no c ea e a non-ze o solu ion. Thus
as
P
app oaches i s
limi , a bi a ily la ge se s o e ices mus be allowed o be a iable,
in o de o
P
no
o
be ini ely s able. Thus since
c,(p)
is always
in ini esimally igid in hese examples, he ecip ocal diag am exis s
o a bi a ily la ge po ions o
G,
(p),
as
P
app oaches i s limi .
.11111.
Jux aposi ions 18,22,23,26,
30
e
31
Ces jux aposi ions ne posseden pas de diag a nmes ecip oques,
mais il n’es pas necessai e de mon e qu’elles ne son pas de
s abili e inie.
On
peu ai e chacun de ces cas
a
I’aide d’a gumen s
pa iculie s (que I’on ome a).
Jux aposi ions 13,
14
e
16
Ce
son les
((
bombes
))
deja men ionnees en in oduc ion. Ces a-
milles de jux aposi ions on comme limi es la jux aposi ion
8,
en ce
qui conce ne les jux aposi ions 13
e
14; e la jux aposi ion 15, pou
la jux aposi ion 16. Les jux aposi ions limi es posseden des eci-
p oques,
e
G,
(p)
es in ini esimalemen igide pou les jux aposi-
ions limi es
(oa
ous
les somme s sau un nomb e ini son ixes).
Pou une pa ie inie ixee de
G,,
il exis e un nomb e ini d’inegali es
qui de e minen la igidi 6 in ini himale de
Gp(p)
(dans un espace
euclidien de dimension ini de de o ma ions in ini esimales), comme
alasec ion
II
(ou
lasec ion
Ill
de la pa ie I).Alo s, ou e pe u ba ion
su
isammen pe i e des inegali es n’en aine pas une solu ion non
nulle. Ainsi, lo sque
P
s’app oche de sa limi e, des ensembles a -
bi ai emen g ands de somme s peu en & e a iable, a in que
P
ne soi pas de s abili e inie. Ainsi, puisque
G,(p)
es oujou s
in ini esimalemen igide dans ces exemples, le diag amme eci-
p oque exis e pou des pa ies a bi ai emen g andes de
G,
(p),
lo sque
P
end e s sa limi e.
.11111.
76
BlBuoGRA
PH
Y
[l]
L.
Asimow and
B.
Ro h
“Tha lgldl y
o
g aphs.”
T ans. A ne . Ma h. SOC. 245 (1975),
An
in oduc ion
o
he basic heo y o
p.279-289.
igidi y.
Une
in oduc ion
B
la heo ie ondamen-
ale de la igidi e.
[2]
L.
Asimow and B. Ro h
“The
lgldl y
o
g aphs
11.”
J. Ma h. Appl.
68
(1979), p.171-190.
A
con inua ion o
Pa
1.
La sui e de la pa ie
1.
[3]
Robe Connelly
“The lgldl y
o
ce ain cabled
amewo ks
and he second o de
lgldl y
o
a bi a ily langula ed
con ex
su iace .”
Ad ances in Ma h. 37, N0.3 (1980),
The i le is he abs ac .
Le i e en es
un
esumd.
p.272-299.
[I]
Robe Connelly
“Rlgld ci cla and sphe a packlngs.
Pa
I:
Flnl e
packing%”
S uc u al Topology, 14 (1988), p.43-60.
The basic gene al heo y used o he
igidi y o packings.
La
hlo ie gene aale de base u ilisee dans
la igidi e des jux aposi ions.
[5]
J.A. Dunn
“Tessella ions wl h pen qons.”
Ma hema ical Gase e, 55, Dec. 1971,
p.366-369.
Follow-up
co espondence
Fxamples
o
ilings wi h pen agons.
Fxemples de pa ages
d
I‘aide de
pen ag ones.
V01.56, p.332-335.
[6]
L.
Fejes
T6 h
Regula Flgum.
Pe ga non P ess (1964).
An
in oduc ion
o
many ideas ela ed o
packing and co e ing p oblems.
Une in oduc ion
B
plusieu s idees
Wes
aux p oblimes de jux aposi ion e de
ecou emen .
[7]
B anko G unbaum and G.C. Shepha d
“A
hle a chy
o
classl lca lon
ma hods
o pa e ns.”
Zei sch i
u
K is allog aphie, 154
A
ca e ul discussion o he me hod o
classi ica ion
o
egula packings.
Une
discussion soignee de la me hode
de classi ica ion
des
jux aposi ions
eguli& es.
(1
981
),
p.163-I 87.
[8]
B.
Ro h and W. Whi eley
“lenseg i y
amewo ks.”
T ans.
o
A.M.S. (1981), p.410-446.
The basics o s a ics and in ini esimal
igidi y o amewo ks wi h cables and
s u s.
Les ondemen s de la igidi d s a ique e
de la igidi e in ini esimaie des cha pen es
de cables e d’e ais.
[8]
Do is Scha schneide
“llllng
he plane wl h cong uen
pen agons.”
Ma h. Mag., Vo1.51, No.1, Jan.1978, p.29-
44.
Mo e examples o ilings
o
he plane
wi h cong uen pen agons.
Enco e des exemples de pa ages du plan
B
I’aide de pen agones cong uen s.