## Abstract

We study the combinatorial and rigidity properties of disc packings with generic radii. We show that a packing of *n* discs in the plane with generic radii cannot have more than 2*n* − 3 pairs of discs in contact. The allowed motions of a packing preserve the disjointness of the disc interiors and tangency between pairs already in contact (modelling a collection of sticky discs). We show that if a packing has generic radii, then the allowed motions are all rigid body motions if and only if the packing has exactly 2*n* − 3 contacts. Our approach is to study the space of packings with a fixed contact graph. The main technical step is to show that this space is a smooth manifold, which is done via a connection to the Cauchy–Alexandrov stress lemma. Our methods also apply to jamming problems, in which contacts are allowed to break during a motion. We give a simple proof of a finite variant of a recent result of Connelly *et al.* (Connelly *et al*. 2018 (http://arxiv.org/abs/1702.08442)) on the number of contacts in a jammed packing of discs with generic radii.

### 1. Introduction

In this paper, we study the existence and rigidity properties of packings of sticky discs with fixed generic radii.

A (planar) packing *P* of *n*≥2 discs is a placement of the discs, with centres ** p** = (

*p*_{1}, …,

*p*_{n}) and fixed radii

**= (**

*r**r*

_{1}, …,

*r*

_{n}), in the Euclidean plane so that their interiors are disjoint. The contact graph of a packing is the graph that has one vertex for each disc and an edge between pairs of discs that are mutually tangent. Figure 1 shows an example of a packing.

#### (a) Sticky disc and framework rigidity

A motion of a packing, called a flex, is one that preserves the radii, the disjointness of the disc interiors, as well as tangency between pairs of discs with a corresponding edge in the contact graph. (The last condition makes the discs ‘sticky’.) A packing is rigid when all its flexes arise from rigid body motions; otherwise, it is flexible.

Since any packing has a neighbourhood on which the contact graph remains fixed along any flex (one must move at least some distance before a new contact can appear), the constraints on the packing are locally equivalent to preserving the pairwise distances between the circle centres. Forgetting that the discs have radii and must remain disjoint and keeping only the distance constraints between the centres, we get exactly ‘framework rigidity’, where we have a configuration ** p** = (

*p*_{1}, …,

*p*_{n}) of

*n*points in a

*d*-dimensional Euclidean space and a graph

*G*; the pair (

*G*,

**) is called a (bar-and-joint) framework. The allowed flexes of the points are those that preserve the distances between the pairs indexed by the edges of**

*p**G*. As with packings, a framework is rigid when all its flexes arise from rigid body motions and otherwise flexible. Given a packing (

**,**

*p***) with contact graph**

*r**G*, we call the framework (

*G*,

**) its underlying framework.**

*p*#### (b) Motivations

Rigidity of sticky disc packings, and the relationship to frameworks, has several related, but formally different, motivations. The first comes from the study of colloidal matter [1], which is made of micrometre-sized particles that interact with ‘short-range potentials’ [2,3] that, in a limit, behave like sticky discs [4] (spheres in three dimensions).

Secondly, there is a connection to jammed packings. Here one has a ‘container’, which can shrink uniformly and push the discs together. In this setting, we do not require any contact graph to be preserved. A fundamental problem is to understand the geometry and combinatorics of maximally dense packings (where the container can shrink no more—full definitions will be given in §4). In a series of papers, Connelly and co-workers [5–7] relate configurations that are locally maximally dense to the rigidity of a related tensegrity (e.g. [8]) over the contact graph. Notably, the recent work in [9] proves results about the number of contacts appearing in such locally maximally dense packings under appropriate genericity assumptions.

Another motivation comes from geometric constraint solving [10], where combinatorial methods are also applied to structures made of discs and spheres.

#### (c) Laman's theorem

Given the relationship between disc packings and associated frameworks, it is very tempting to go further and apply the methods of *combinatorial* rigidity (e.g. [11]) theory to infer geometric or physical properties from the contact graph alone. Several recent works in the soft matter literature [12–14] use such an approach.

The combinatorial approach is attractive because we have a very good understanding of framework rigidity in dimension 2, provided that ** p** is not very degenerate.

#### Definition 1.1.

A vector in ${\mathbb{R}}^{N}$ is called generic if its coordinates are algebraically independent over
$\mathbb{Q}$. A point configuration ** p** of

*n*points in ${\mathbb{R}}^{d}$ is called generic if the coordinates of its points (a vector in ${\mathbb{R}}^{dn}$) are algebraically independent over $\mathbb{Q}$.

Almost all configurations are generic, so generic configurations capture the general case. Moreover, all the results in this paper remain true if we simply avoid the zero set of a specific but unspecified set of polynomials with rational coefficients (i.e. the results hold on a Zariski open subset, defined over $\mathbb{Q}$, of the appropriate configuration space).

The following combinatorial notion captures the 2-dimensional case of a counting heuristic due to Maxwell [15].

#### Definition 1.2.

Let *G* = (*V*, *E*) be a graph with *n* vertices and *m* edges. A graph *G* is Laman-sparse if, for every subgraph on *n*′ vertices and *m*′ edges, *m*′≤2*n*′ − 3. If, in addition, *m* = 2*n* − 3, *G* is called a Laman graph.

The following theorem, which combines the results of Asimow & Roth [16] and Laman [17], characterizes rigidity and flexibility of generic frameworks in the plane.

#### Theorem 1.3.

*Let* *G* *be a graph with* *n* *vertices and* *p**a generic configuration of* *n* *points in dimension* 2. *Then the framework* (*G*, ** p**)

*is rigid if*

*G*

*contains a Laman graph as a spanning subgraph and otherwise flexible.*

Theorem 1.3 makes generic rigidity and flexibility a combinatorial property that can be analysed very efficiently using graph-theoretic algorithms [18,19], even on large inputs. Of course, one needs to make the modelling assumption that the process generating ** p** is generic. If not, then the use of combinatorial methods is not formally justified.

In fact, the genericity^{1} hypothesis is essential: one may find (necessarily non-generic) ** p** for which a framework (

*G*,

**) is flexible and**

*p**G*is a Laman graph (e.g. [20]); conversely, there are non-generic frameworks that are rigid but have too few edges to be rigid with generic

**(e.g. [21]).**

*p*^{2}

#### (d) Packing Laman question

The starting point for this paper is the observation that configurations arising from packings with discs in contact are not generic. Thus, the theory of generic bar frameworks does not apply directly to packings.

The most general situation for packings is the (extremely) ‘polydisperse’ case in which the radii *r*_{i} are algebraically independent over $\mathbb{Q}$. Even with generic radii, the configuration of disc centres could be very degenerate relative to picking ** p** freely. For an edge

*ij*in

*G*, the contact constraint is

*n*degrees of freedom (the radii) to pick the edge lengths, instead of the 2

*n*− 3 available to a general (

*G*,

**) with**

*p**G*a Laman graph. Thus, the underlying

**of a disc packing with a Laman contact graph is certainly not generic, and so theorem 1.3 does not apply. We need another formal justification for analysing packings combinatorially.**

*p*#### (e) Packing non-existence question

Beyond rigidity, there is the general question of what graphs can appear as the contact graph of a packing with generic radii. Once we fix ** r**, there are 2

*n*− 3 non-trivial degrees of freedom in packing

**. If a graph**

*p**G*has

*n*vertices, each of its

*m*edges contributes a constraint of the type (1.1). Thus, when

*m*> 2

*n*− 3, we expect, heuristically, that either no

**exists or**

*p***satisfies some additional polynomial relation.**

*r*##### (i) Main result

Our main result is a variant of theorem 1.3 for packings that answers both the rigidity and non-existence questions under the assumption of generic radii. To state our theorem, we need one more rigidity concept, which is a linearization of rigidity.

##### Definition 1.4.

An infinitesimal flex ** p**′ of a

*d*-dimensional bar-and-joint framework (

*G*,

**) is an assignment of a vector ${\mathbf{p}}_{i}^{\prime}\in {\mathbb{R}}^{d}$ to each vertex of**

*p**G*so that, for all edges

*ij*of

*G*,

An infinitesimal flex for a disc packing is simply an infinitesimal flex of its underlying bar-and-joint framework. A packing is infinitesimally rigid if its underlying bar-and-joint framework is.

Since rigidity does not imply infinitesimal rigidity, infinitesimal rigidity is a more stringent condition to place on a framework than rigidity. Generically, however, the two concepts coincide [16].

Our main result is as follows.

##### Theorem 1.5.

*Let* *P* *be a packing of* *n* *discs in the Euclidean plane* ${\mathbb{R}}^{2}$ *with generic radii* *or even just generic radii ratios**Then the contact graph* *G* *of* *P* *has at most* 2*n* − 3 *edges and is Laman-sparse and planar. Moreover**if* *P has* 2*n* − 3 *contacts**it is rigid and infinitesimally rigid. If the number of contacts is fewer**then* *P* *is flexible and infinitesimally flexible.*

Figure 2 shows a ‘real world’ example of a packing with radii that exhibit generic behaviour.

We note that the upper bound on the number of contacts does not rely on any rigidity properties of *P*, and, indeed, a similar upper bound will appear in §4, even though the rigidity statement is different.

The rigidity characterization has an algorithmic consequence. Since it only requires checking the total number of contacts, generic rigidity of a graph known to be the contact graph of a disc packing with generic radii can be checked in linear time. By contrast, for general graphs, the Laman sparsity condition must be verified for all subgraphs. The best known algorithms [18,19,22] for this task have super-linear running times.

As with theorem 1.3, genericity is essential to theorem 1.5. If all the radii are the same, the triangular lattice packing gives a packing with more than 2*n* − 3 contacts. More generally, the Köbe–Andreev–Thurston theorem [23, theorem 13.6.2] says that any planar graph can appear as the contact graph of some packing (which necessarily has non-generic radii when *m* > 2*n* − 3).

One can also construct non-generic examples of packings with fewer than 2*n* − 3 contacts that are rigid (figure 3*a*) and at least 2*n* − 3 contacts that are flexible (figure 3*b*).

In §4 we also provide a bonus result characterizing the number of contacts that appear in a maximally jammed packing where the boundary is formed by three touching large exterior discs.

#### (f) Other related work

General questions of whether combinatorial characterizations of rigid frameworks remain valid in the presence of special geometry have been addressed before. Notably, our ‘packing Laman question’ is similar in flavour to the ‘molecular conjecture’ of Tay & Whiteley [25], which was solved by Katoh & Tanigawa [26].

### 2. The packing manifold

To prove our theorem, we start by defining the packing manifold of a contact graph.

### Definition 2.1.

Let *G* be a graph with *n* vertices and *m* edges. We think of a disc packing (** p**,

**) as a point in ${\mathbb{R}}^{3n}$. Let ${S}_{G}\subset {\mathbb{R}}^{3n}$ be the set of disc packings where (only) the edges in**

*r**G*correspond to the circle pairs that are in contact.

*S*

_{G}is a semi-algebraic set defined over $\mathbb{Q}$.

Our goal in this section is to prove that (when not empty) *S*_{G} is a smooth manifold and of the expected dimension 3*n* − *m*.

Let *P* be a point of *S*_{G}. Since exactly the pairs of discs corresponding to the edges of *G* are in contact, the constraints defining *S*_{G} near *P* are *m* equations of the type (1.1).

We now compute the Jacobian matrix *M* for these constraints at *P*. The matrix *M* is *m*-by-3*n*, with one row per contact edge, and three columns corresponding to each vertex *i* of *G*: two for *p*_{i} and one for *r*_{i}.

Differentiating (1.1) with respect to the coordinates of *p*_{i}, *p*_{j}, *r*_{i} and *r*_{j} in turn, we find that the row corresponding to an edge *ij* of *G* has the following pattern:

*i*and

*j*are in contact to make the simplification

To prove that *S*_{G} is smooth, we only need to show that *M* has rank *m* at every point *P*. We will establish this via a connection between row dependencies in *M* and a specific kind of equilibrium stress in planar frameworks.

### Definition 2.2.

An edge-length equilibrium stress *ω* of a framework (*G*, ** p**) is a non-zero vector in ${\mathbb{R}}^{m}$ that satisfies

*i*∈

*V*(

*G*). The sums in (2.2) and (2.3) are over neighbours

*j*of

*i*in

*G*.

An edge-length equilibrium stress is strict if it has no zero coordinates.

Vectors *ω* satisfying only (2.2) are called equilibrium stresses and play a fundamental role in the theory of bar-and-joint frameworks. Equation (2.3) is the new part of the definition which is relevant to packings.

### Remark 2.3.

W. Lam (2018, personal communication) has shown that edge-length equilibrium stresses are equivalent to the holomorphic quadratic differentials of Köbe type from [27]. In particular, for planar frameworks without boundary (in the sense of [27]), there are none.

Interestingly, the main theorem of [27] says that a planar embedded framework has an edge-length equilibrium stress if and only if a triangulation of its dual medial graph has an equilibrium stress satisfying the formally different condition $\sum _{j}{\omega}_{ij}\parallel {\mathbf{p}}_{i}-{\mathbf{p}}_{j}{\parallel}^{2}=0$ at each vertex. This condition is connected to orthogonal circle patterns [27] and discrete minimal surfaces [28].

We defined edge-length equilibrium stresses because they are the co-kernel vectors of *M*.

### Lemma 2.4.

*Let* *G* *be a graph**P*∈*S*_{G} *be a packing and* (*G*, ** p**)

*its underlying framework. Then*

*ω*

*is an edge-length equilibrium stress of*(

*G*,

**)**

*p**if and only if*

*ω*

*is in the co-kernel of the packing constraint Jacobian*

*M*.

### Proof.

Equations (2.2) and (2.3) are equivalent to *ω*^{t}*M* = 0 written down column by column. ▪

Next, we want to show that there can be no co-kernel vector for the underlying framework of a disc packing *P*. We will do this by showing a stronger statement, namely that there can be no edge-length equilibrium stress for *any* bar-and-joint framework with a planar embedding. (When *m* > 2*n* − 3, there will always be equilibrium stresses of any framework (*G*, ** p**). However, none of them will be an edge-length equilibrium stress, satisfying equation (2.3) when (

*G*,

**) has a planar embedding.)**

*p*### Definition 2.5.

We say that a framework (*G*, ** p**) is a planar embedded framework if all the points in the configuration

**are distinct and correspond to the vertices of a non-crossing, straight line drawing of**

*p**G*in the plane. (In particular, the existence of a planar embedded framework (

*G*,

**) implies that**

*p**G*is a planar graph.)

### Definition 2.6.

Given a planar embedded framework (*G*, ** p**) and a strict edge-length equilibrium stress

*ω*, we can assign a sign in { + , − } to each undirected edge

*ij*using the sign of

*ω*

_{ij}. This assignment gives us a sign vector.

Given a sign vector on a planar embedded framework we can define the index *I*_{i} as the number of times the sign changes as we traverse the edges in order around vertex *i*. (We use the planar embedding to get the cyclic ordering of edges at each vertex.)

The index *I*_{i} is always even.

The following is Cauchy's index lemma, which can be proven using Euler's formula. For a proof, see [29, lemma 5.2] or [30, p. 87].

### Lemma 2.7.

*Let* (*G*, ** p**)

*be a planar embedded framework and let*

*s*

*be a sign vector. Then*$\sum _{i}{I}_{i}\le 4n-8$.

*Thus there must be at least one vertex with an index of either*0

*or*2.

Next, we establish the following geometric lemma.

### Lemma 2.8.

*Let* (*G*, ** p**)

*be a planar embedded framework with a strict edge-length equilibrium stress vector*

*ω*.

*Let*

*s*

*be the associated sign vector and*

*I*

*be the associated index vector. For each vertex*

*i*

*the index*

*I*

_{i}

*is at least*4.

### Proof.

Suppose some vertex *i* has fewer than four sign changes. If it has zero sign changes, then it cannot satisfy equation (2.3), as all lengths are positive. So now let us suppose that it has two sign changes.

With only two sign changes, the edges from at least one of the signs (say −) must be in a wedge of angle 2*θ* < *π*.

Euclidean images of ** p** have the same edge-length equilibrium stresses, so we may assume that the positive part of the

*x*-axis is the bisector of the wedge. The 2-dimensional equilibrium condition of equation (2.2) must hold after projection along any direction, including onto the

*x*-axis, since (2.2) is invariant under any affine transformation (e.g. [31]).

Let *N*^{+} denote the neighbours of *i* connected by edges with positive sign and *N*^{−} the neighbours connected by negatively signed edges. Let *p*^{x}_{i} be the *x*-coordinate of the point *p*_{i}. We then get:

*j*∈

*N*

^{+}(outside the wedge), we have

*j*∈

*N*

^{−}(inside the wedge), we have

See figure 4 for an illustration of this argument. Understanding which, necessarily non-planar, frameworks can have edge-length equilibrium stresses would be interesting.

### Remark 2.9.

Lemma 2.8 can also be reduced to the the Cauchy–Alexandrov stress lemma [29, lemma 5.2], which says that an equilibrium stress satisfying equation (2.2) in three dimensions must have at least four sign changes at a strictly convex vertex of a polytope.

In the reduction, we place a vertex with two sign changes at the origin and lift its neighbours from (*x*, *y*) to $(x,y,\sqrt{{x}^{2}+{y}^{2}})$. If the 3-dimensional equilibrium equation holds (2.2) at this vertex, then both of (2.2) and (2.3) hold in the plane.

The index and stress lemmas are the two central ingredients in a proof of Cauchy's theorem on the (infinitesimal) rigidity of convex polyhedra [30].

Putting together the index lemma (2.7) and geometric lemma (2.8), we obtain the following lemma.

### Lemma 2.10.

*Let* (*G*, ** p**)

*be a planar embedded framework. Then it cannot have a non-zero edge-length equilibrium stress vector.*

### Proof.

If (*G*, ** p**) has an edge-length equilibrium stress vector, then, by removing edges with 0 stress coefficients, we obtain a subframework (

*G*′,

**′) with a strict edge-length equilibrium stress vector. A strict edge-length equilibrium stress vector would form a contradiction between lemmas 2.7 and 2.8. ▪**

*p*### Remark 2.11.

A similar statement and proof to lemma 2.10, phrased in terms of inversive distances [32], was found independently by Bowers *et al.* [33].

We are ready to prove the main result of this section.

### Proposition 2.12.

*The set* *S*_{G}*if not empty**is a smooth submanifold of dimension* 3*n* − *m*.

### Proof.

Let *P* be a point in *S*_{G}. It has the edges of *G* in contact and no other pairs of discs in contact in a sufficiently small neighbourhood. Thus restricted to this neighbourhood, *S*_{G} is exactly defined by the contact constraints of equation (1.1). Meanwhile, the contact graph creates a planar embedded framework. From lemmas 2.4 and 2.10, there can be no co-kernel vector, and hence the Jacobian matrix has rank *m*. By the implicit function theorem, *S*_{G} restricted to some neighbourhood of *P* is a smooth manifold of dimension 3*n* − *m*. ▪

### Remark 2.13.

The Köbe–Andreev–Thurston theorem implies that *S*_{G} is non-empty provided that *G* is planar [23, theorem 13.6.2].

### 3. Finishing the proof

### Definition 3.1.

Let *π* be the projection (** p**,

**)↦**

*r***taking a disc packing to its vector of radii in ${\mathbb{R}}^{n}$.**

*r*### Definition 3.2.

A *π*-kernel vector of a disc packing *P* with contact graph *G* is a tangent vector to *S*_{G} of the form (** p**′, 0). These vectors form the kernel of the linearization of the map

*π*.

### Lemma 3.3.

*The* *π-kernel vectors of a disc packing* (** p**,

**)**

*r**with contact graph*

*G*

*are infinitesimal flexes of the underlying bar framework*(

*G*,

**).**

*p*### Proof.

As in the proof of proposition 2.12, we have the *m*-by-3*n* Jacobian matrix *M* with rank *m*. Tangent vectors to *S*_{G} are thus (right) kernel vectors (** p**′,

**′) of**

*r**M*. From equation (2.1), the tangent vectors (

**′,**

*p***′) to**

*r**S*

_{G}are exactly the vectors satisfying

*π*-kernel vectors are defined as the tangent vectors with

**′ = 0, giving us**

*r**π*-kernel vectors of

*M*are exactly the infinitesimal flexes of the underlying framework (

*G*,

**). ▪**

*p*We now recall a standard definition and result from differential topology.

### Definition 3.4.

Let *X* and *Y* be smooth manifolds of dimension *m* and *n*, respectively. A smooth map *f*:*X* → *Y* is a submersion at a point *x*∈*X* if the linearization d*f*_{x}:*T*_{x}*X* → *T*_{f(x)}*Y* at *x* is surjective. A point *x*∈*X* is called a regular point of *f* if *f* is a submersion at *x*; otherwise, *x* is a critical point of *f*.

A point *y*∈*Y* is called a regular value of *f* if *f*^{−1}(*y*) consists of only regular points (or is empty); otherwise, *y* is a critical value.

The following is the semi-algebraic version of Sard's theorem.

### Theorem 3.5.

*Let* *X* *and* *Y* *be smooth semi-algebraic manifolds of dimensions* *m* *and* *n* *defined over* $\mathbb{Q}$ *and* *f*:*X* → *Y* *a rational map. Then the critical values of* *f* *are a semi-algebraic subset of* *Y* *defined over* $\mathbb{Q}$*and of dimension strictly less than* *n*.

### Proof.

Confirmation that the critical values are semi-algebraic and of lower dimension can be found in [34, theorem 9.6.2]. That the field of definition does not change follows from the fact that the critical points lie in a semi-algebraic subset defined over $\mathbb{Q}$ (by the vanishing of a determinant), and then the critical values do because quantifier elimination preserves the field of definition [35, theorem 2.62]. ▪

### Lemma 3.6.

*Let* *r**be a generic point in* ${\mathbb{R}}^{n}$ *and let* *P*: = (** p**,

**)**

*r**be a disc packing with*

*m*

*contacts and contact graph*

*G*.

*Then the linear space of*

*π-kernel vectors is of dimension*2

*n*−

*m*.

Moreover** r** and contact graph

*G*form a smooth

*n*−

*m*.

### Proof.

Because *P* exists, *S*_{G} is non-empty, and so, by proposition 2.12, is a smooth semi-algebraic manifold of dimension 3*n* − *m*. The map $\pi :{S}_{G}\to {\mathbb{R}}^{n}$ is a polynomial map, so theorem 3.5 applies, making all the critical values of *π* non-generic.

Since ** r** is generic, it must be a regular value of

*π*. Hence

*P*is a regular point, and the linearization of

*π*at

*P*has rank

*n*. Its kernel then has a dimension (3

*n*−

*m*) −

*n*= 2

*n*−

*m*.

Finally, the set of packings with radii ** r** and contact graph

*G*is simply

*π*

^{−1}(

**). The preimage theorem (e.g. [36, p. 21]) implies that**

*r**π*

^{−1}(

**) is smooth and of the same dimension as the kernel of d**

*r**π*

_{P}. ▪

The rank of d*π*_{P} is never larger than the dimension of *S*_{G}, which is 3*n* − *m*. If the dimension of *S*_{G} is less than *n*, d*π*_{P} cannot be surjective for any *P* in *S*_{G}, making every point in *S*_{G} a critical point. Hence, for ** r** to be generic, we must have

*m*≤2

*n*. We will improve the preceding bound on

*m*momentarily.

### Remark 3.7.

The proof of lemma 3.6 shows that ** r** does not need to be generic for the conclusion to hold. It just needs to be a regular value of

*π*. By theorem 3.5, the regular values of

*π*are a Zariski open subset of ${\mathbb{R}}^{n}$, defined over $\mathbb{Q}$.

We can now prove our main result.

### Proof of theorem 1.5.

Since we are in dimension *d* = 2, there is a 3-dimensional space of trivial infinitesimal motions of any framework (*G*, ** p**).

The packing *P*: = (** p**,

**) has**

*r***generic by hypothesis. Lemma 3.6 then implies that the space of**

*r**π*-kernel vectors has dimension 2

*n*−

*m*. The presence of a 3-dimensional space of trivial infimitesimal motions then implies that 2

*n*− 3≥3, so

*m*≤ 2

*n*− 3. The same argument, applied to each subgraph of

*G*, shows that

*G*is Laman-sparse.

If *G* has *m* = 2*n* − 3 edges, then lemmas 3.3 and 3.6 imply that (*G*, ** p**) has only a 3-dimensional space of infinitesimal flexes and is thus infinitesimally rigid and hence rigid. Otherwise

*m*< 2

*n*− 3, and so the

*π*

^{−1}(

**) has dimension at least 4 by lemma 3.6. As the space of frameworks related to (**

*r**G*,

**) by rigid body motions is only 3-dimensional, it follows that (**

*p**G*,

**) is flexible. A flexible framework is always infinitesimally flexible.**

*p*Since rigidity properties are invariant with respect to global scaling, we only need genericity of the radii ratios. ▪

### 4. Isostatic jamming

In this section, we use the technology developed above to prove a result about ‘jammed packings’. In the light of [9], the fact that this can be proven is not surprising. Our contribution is to show how the elementary methods we used to treat sticky discs adapt easily to jamming questions.

#### (a) Rigidity preliminaries for jamming

Loosely speaking, we consider a set of discs in the plane with a fixed set of radii. We do not allow the discs to ever overlap. The discs are not sticky. Now we suppose that there is some boundary shape surrounding these discs that are uniformly shrinking. The boundary will start pressing the discs together, and, eventually, the boundary can shrink no more. At this point in the process, we will say that the packing is ‘locally maximally dense’.

An equivalent way to study this problem is to assume that the boundary shape stays fixed and that the disc radii are all scaling up uniformly, maintaining their radii ratios. We will use this interpretation.

The literature considers a number of different boundary shapes, including convex polyhedra (e.g. [6]) and flat tori (e.g. [9,12]). Here, we consider a boundary formed by three large touching exterior discs. This kind of boundary, which we will call a ‘tri-cusp’, has the advantage that it can be modelled by the same type of constraints as those on the interior discs.

#### Definition 4.1.

A packing inside of a tri-cusp is a disc packing in the plane where the first three discs are in mutual contact, and the remaining *n* − 3 ‘internal’ discs are in the interior tri-cusp shape bounded by these first three discs. The packing will have some contact graph *G* that includes the triangle {1, 2, 3} (figure 5).

To represent the internal radii ratios we define, for *j* = 4, 5, …, *n* − 1, the ratio ${\overline{r}}_{j}:={r}_{j}/{r}_{n}$.

#### Definition 4.2.

We say that a disc packing in a tri-cusp is locally maximally dense if there is no nearby tri-cusp packing with the same $\{{r}_{1},{r}_{2},{r}_{3},{\overline{r}}_{4},\dots ,{\overline{r}}_{n-1}\}$ that has a higher area of coverage within the tri-cusp. The outer three discs must maintain contact.

Local maximal density can be studied using a notion related to infinitesimal rigidity.

#### Definition 4.3.

Given a disc packing in a tri-cusp (** p**,

**), with contact graph**

*r**G*, an infinitesimal tensegrity flex is a vector

**′ that satisfies**

*p*on the three edges of the outer triangle (figure 5), and satisfies

Any infinitesimal flex, in the sense of definition 1.4, is also an infinitesimal tensegrity flex. We say that the packing is infinitesimally collectively jammed if the only infinitesimal tensegrity flexes ** p**′ are trivial infinitesimal flexes of (

*G*,

**). There is always a 3-dimensional space of trivial infinitesimal flexes.**

*p*#### Remark 4.4.

The terminology ‘tensegrity flex’ comes from the fact that a vector ** p**′ satisfying equations (4.1) and (4.2) is an infinitesimal flex of a tensegrity structure where the edges of the outer triangle are fixed-length bars, and all of the internal edges are ‘struts’ that can increase, but not decrease, their length during a flex. (See the notes [8] for a detailed treatment of tensegrities.)

These two notions are related by the following theorem of Connelly [5].

#### Theorem 4.5.

*If a packing in a tri-cusp is infinitesimally collectively jammed then it is locally maximally dense. If a packing in a tri-cusp is locally maximally dense**then there is a sub-packing that is infinitesimally collectively jammed.*

When the tri-cusp packing is locally maximally dense, then the maximal infinitesimally collectively jammed sub-packing forms a ‘spine’ in which none of the discs can expand, even non-uniformly. Discs that are not part of the spine are called ‘rattlers’ in the literature. Rattlers can expand in any desired way.

##### (i) Bonus result: finite isostatic theorem

The main result of this section is the following ‘isostatic’ theorem.

##### Theorem 4.6.

*Let* *P*: = (** p**,

**)**

*r**be a packing in a tri-cusp. Suppose that the vector*$\overline{\mathbf{r}}:=\{{r}_{1},{r}_{2},{r}_{3},{\overline{r}}_{4},\dots ,{\overline{r}}_{n-1}\}$

*is generic in*${\mathbb{R}}^{n-1}$.

*Then*

*P*

*cannot have more than*2

*n*− 2

*contacts. If*

*P*

*is infinitesimally collectively jammed then it has exactly*2

*n*− 2

*contacts.*

The genericity assumption in theorem 4.6 is only on $\overline{\mathbf{r}}$ (as opposed to ** r** in theorem 1.5), so the relative scale between the inner discs and the outer three need not be generic. The weaker genericity hypothesis will allow for the possibility of one (and only one) extra contact in the packing. The upper bound of 2

*n*− 2 contacts does not depend on any notions of density or jamming. When there are fewer than 2

*n*− 2 contacts, the theorem says that there must exist a a non-trivial infinitesimal tensegrity flex, thus precluding infinitesimal collective jamming.

Combining theorems 4.6 and 4.5, we obtain the following corollary.

##### Corollary 4.7.

*Let* *P*: = (** p**,

**)**

*r**be a locally maximally dense packing in a tri-cusp with the vector*$\overline{\mathbf{r}}:=\{{r}_{1},{r}_{2},{r}_{3},{\overline{r}}_{4},\dots ,{\overline{r}}_{n-1}\}$

*generic in*${\mathbb{R}}^{n-1}$.

*Then*

*P*

*has a sub-packing in a tri-cusp*

*P*′

*of*

*n*′

*discs with*2

*n*′ − 2

*contacts among them that is infinitesimally collectively jammed.*

##### Proof of theorem 4.6.

Let us redefine *S*_{G}, in this section only, to be the set of tri-cusp packings with a fixed contact graph *G*. As above (proposition 2.12), *S*_{G} (if not empty) is smooth and of dimension 3*n* − *m*.

Let us redefine our projection *π*, in this section only, to be the map from ${\mathbb{R}}^{3n}$ to ${\mathbb{R}}^{n-1}$, which maps (** p**,

**) to $\{{r}_{1},{r}_{2},{r}_{3},{\overline{r}}_{4},\dots ,{\overline{r}}_{n-1}\}$. With the new definition of**

*r**π*, the preimage ${\pi}^{-1}(\overline{\mathbf{r}})$ in

*S*

_{G}corresponds to packings with contact graph

*G*, where the outer three discs are fixed (up to a Euclidean isometry) and the internal radii ratios are fixed.

Next, we redefine a *π*-kernel vector at (** p**,

**)∈**

*r**S*

_{G}to be a tangent vector of

*S*

_{G}that is in the kernel of the linearization of

*π*. Following the proof of lemma 3.6, except with an image of dimension

*n*− 1 instead of

*n*, we see that the space of

*π*-kernel vectors above a generic (and so regular) value in ${\mathbb{R}}^{n-1}$ will be of dimension 2

*n*−

*m*+ 1. Since the space of

*π*-kernel vectors above any point contains a 3-dimensional subspace of trivial motions, we obtain 2

*n*−

*m*+ 1≥3. Hence

*m*≤2

*n*− 2, giving us the first statement.

Let us now explore the implications of *m* < 2*n* − 2, which means that the *π*-kernel is of dimension at least 4. We note for later that $\mathrm{\partial}{\overline{r}}_{j}/\mathrm{\partial}{r}_{j}=1/{r}_{n}$ and $\mathrm{\partial}{\overline{r}}_{j}/\mathrm{\partial}{r}_{n}=-{r}_{j}/{r}_{n}^{2}$. Also, recall, from equation (3.1), that (** p**′,

**′) is tangent to**

*r**S*

_{G}iff it satisfies

**′,**

*p***′) to be a**

*r**π*-kernel vector, it must additionally satisfy, for

*j*= 1, 2, 3,

*j*= 4, …,

*n*,

Equations (4.3) and (4.4) imply that the *r*′_{j} are either all non-positive or all non-negative. After negating, if necessary, we conclude that if (** p**′,

**′) is a**

*r**π*-kernel vector, then

**′ is an infinitesimal tensegrity flex. (Note that the converse is not true. An infinitesimal tensegrity flex vector**

*p***′ does not necessarily have a corresponding**

*p**π*-kernel vector. This ties into the discussion of §4a(ii).)

Thus, if the *π*-kernel at (** p**,

**) is of dimension at least 4, then we will be able to find a non-trivial infinitesimal tensegrity flex. Hence,**

*r**P*is not infinitesimally collectively jammed. ▪

##### Remark 4.8.

The lower bound aspect of theorem 4.6, namely that infinitesimal collective jamming requires at least 2*n* − 2 contacts, is already established in [6]. The results in [6] do not require genericity and generalize to higher dimensions.

##### (ii) No converse

There is a major difference between theorems 1.5 and 4.6 in that simply having generic radii and 2*n* − 2 contacts does not guarantee that a packing in a tri-cusp is infinitesimally collectively jammed or even locally maximally dense. Figure 5*b* shows an example.

Such examples show an essential difference between the inequalities in the jamming set-up and the equalities defining the sticky behaviour of sticky discs. In fact, if the discs in figure 5*b* are forced to be sticky (but are still allowed to grow uniformly), then the example becomes rigid and infinitesimally rigid in an appropriate sense.

Interestingly, the papers [12–14] that partially motivated our interest in these problems use counting to analyse simulated jammed packings, essentially treating them as if the discs were sticky.

##### (iii) Relationship to the flat torus isostatic theorem

The isostatic theorem with a flat torus as the container was proven in [9] using very general results of Guo [37] on circle patterns in piecewise-flat surfaces. Such methods could also be applied to the tri-cusp setting.

It would be interesting to know if our methods can be extended to the torus. Such an extension would require us to show that the corresponding *S*_{G} set of *n* discs on a flat torus (with flexible metric and fixed affine structure) is smooth and of the expected co-dimension, *m*. We do not know how to do that, and establishing the analogue of lemma 2.10 for frameworks embedded in a torus might be interesting in its own right.

### 5. Open problems

#### (a) Existence

Our paper proves certain properties about disc packings with generic radii. There certainly are classes of planar Laman graphs for which we can build packings with generic radii. For a simple example, starting with a triangle, we can sequentially add on discs on the exterior of the packing, each time using generic radii and adding two contacts. But, importantly, we do not know about the existence of such packings for *all* planar Laman graphs. As in remark 2.13, we can see that if *G* is any planar graph, then there must exist some disc packings with contact graph *G*. But this reasoning does not tell us about the genericity of the resulting radii.

#### Question 5.1.

Is the following claim true? Let *G* be planar and Laman. Then there is a packing *P* with contact graph *G* that has generic radii.

If there is a packing with generic radii, then there will at least be an open ball of radii that can be used with *G*.

The generalization of question 5.1 to ball packings in three dimensions with contact graphs that are ‘3*n* − 6 sparse’ (i.e. that satisfy the generalization of Maxwell's counting heuristic to dimension 3) appears to be false. The double banana graph [38, fig. 2] can appear as the packing graph of eight balls, but it seems that such a packing will need carefully selected radii. Of course, the double banana is not a generically isostatic graph. So in three dimensions, we can weaken the existence question and only consider contact graphs that are generically isostatic.

The following is an even stronger claim.

#### Question 5.2.

Is the following claim true? Let *P* be any disc packing where its contact graph *G* is planar and Laman. Then there is a nearby packing *P*′ with generic radii and the same contact graph.

We can give a partial answer.

#### Proposition 5.3.

*Assuming that* *P* *is infinitesimally rigid**the answer to question 5.2 is ‘yes’.*

#### Proof sketch.

If (*G*, ** p**) is an infinitesimally rigid framework of a Laman graph, then the vector

**of**

*l**m*edge lengths of (

*G*,

**) is a regular point of the map that measures edge lengths. The constant rank theorem (e.g. [39, theorem 9.32]) then implies that there is a neighbourhood**

*p**N*of

**in ${\mathbb{R}}^{m}$ consisting of edge-length measurements arising from frameworks close to (**

*l**G*,

**).**

*p*Next let *L* be the linear map from ${\mathbb{R}}^{n}$ to ${\mathbb{R}}^{m}$ defined by *L*_{ij}(** r**): = (

*r*

_{i}+

*r*

_{j}), where

*ij*ranges over the edges of

*G*. The image of

*L*is a linear space. (Restricted to packing with contact graph

*G*, the map

*L*measures the edge lengths of pairs of discs in contact, but we want the more general setting.)

By assumption, *P* = (** p**,

**) is infinitesimally rigid. Hence,**

*r**N*and

**as in the first paragraph are defined for the underlying framework (**

*l**G*,

**). Since**

*p**L*(

**) =**

*r***, the image of**

*l**L*intersects the interior of

*N*. Call this intersection

*N*′.

For a sufficiently small perturbation ** r**′ of

**, we have**

*r**L*(

**′) in**

*r**N*′. This means there is a

**′ close to**

*p***so that (**

*p**G*,

**′) has edge lengths**

*p**L*(

**′). By picking**

*r***′ close enough to**

*r***,**

*r***′ can be made close enough to**

*p***to guarantee that (**

*p***′,**

*p***′) is a packing with contact graph**

*r**G*(i.e. with no new contacts or disc overlaps).

Since any neighbourhood of ** r** contains a generic

**′, we obtain a nearby packing with generic radii. ▪**

*r*#### Remark 5.4.

If *P* is not infinitesimally rigid, the proof of proposition 5.3 above fails at the first step. Without infinitesimal rigidity, the neighbourhood *N* may not exist, in which case the image of *L* could be tangent to the set of achievable lengths at ** l**.

The answer to question 5.2 is ‘no’ if we relax the packing-overlap constraint, as shown in figure 6, even though all the disc contacts are external.

#### (b) Removing inequalities

The results of this paper rely on the fact that the underlying framework is a planar embedding, which is guaranteed by the packing inequalities.

In the algebraic setting, we ignore the packing inequalities and enforce only the equality constraints ∥*p*_{i} − *p*_{j}∥^{2} = (*r*_{i} + *r*_{j})^{2} on the edges of our graph *G*. The analogous object to *S*_{G} in the algebraic setting is an algebraic variety (as opposed to a semi-algebraic set).

#### Question 5.5.

In the algebraic setting, do the results of theorem 1.5 still hold?

#### (c) Three dimensions

The topics of this paper can be considered in three dimensions, where discs are replaced with balls. The natural target contact number would then become 3*n* − 6.

#### Question 5.6.

Do the results of theorem 1.5 generalize to three dimensions?

The authors of [10] conjecture that question 5.6 has a positive answer.

Interestingly, it conceivable that the Maxwell counting heuristic is sufficient for generic rigidity for generic radius ball packing. Maxwell counting is not sufficient for bar frameworks, with that pesky double banana as a counter example. But it appears that the double banana cannot appear as the contact graph of a ball packing with generic radii.

### Data accessibility

This article has no additional data.

### Authors' contributions

R.C., S.J.G. and L.T. devised and conducted the research and wrote the paper.

### Competing interests

We declare we have no competing interests.

### Funding

R.C. is partially supported by NSF grant no. DMS-1564493. S.J.C. is partially supported by NSF grant no. DMS-1564473.

## Acknowledgements

We thank Meera Sitharam and Wai Yeung Lam for helpful feedback on an earlier version of this paper. The anonymous referees made a number of suggestions that improved the exposition.

## Footnotes

### References

- 1.
Manoharan VN . 2015 Colloidal matter: packing, geometry, and entropy.**Science**,**349**1253751 . (doi:10.1126/science.1253751) Crossref, PubMed, Web of Science, Google Scholar - 2.
Arkus N, Manoharan VN, Brenner MP . 2009 Minimal energy clusters of hard spheres with short range attractions.**Phys. Rev. Lett.**,**103**118303 . (doi:10.1103/PhysRevLett.103.118303) Crossref, PubMed, Web of Science, Google Scholar - 3.
Meng G, Arkus N, Brenner MP, Manoharan VN . 2010 The free-energy landscape of clusters of attractive hard spheres.**Science**, 560–563. (doi:10.1126/science.1181263) Crossref, PubMed, Web of Science, Google Scholar**327** - 4.
Holmes-Cerfon M, Gortler SJ, Brenner MP . 2013 A geometrical approach to computing free-energy landscapes from short-ranged potentials.**Proc. Natl Acad. Sci. USA**, E5–E14. (doi:10.1073/pnas.1211720110) Crossref, PubMed, Web of Science, Google Scholar**110** - 5.
Connelly R . 2008 Rigidity of packings.**Eur. J. Combin.**, 1862–1871. (doi:10.1016/j.ejc.2008.01.009) Crossref, Web of Science, Google Scholar**29** - 6.
Connelly R . 1988 Rigid circle and sphere packings. Part I: finite packings [Juxtapositions rigides de cercles et de sphères. I. Juxtapositions finies].*Structural Topology***14**, 43–60. Dual French–English text. See https://upcommons.upc.edu/handle/2099/1044. Google Scholar - 7.
Donev A, Torquato S, Stillinger FH, Connelly R . 2004 A linear programming algorithm to test for jamming in hard-sphere packings.**J. Comput. Phys.**, 139–166. (doi:10.1016/j.jcp.2003.11.022) Crossref, Web of Science, Google Scholar**197** - 8.
Williams WO . 2016 A primer on the mechanics of tensegrity structures. See http://www.math.cmu.edu/~wow/papers/newprimer.pdf. Google Scholar - 9.
Connelly R, Gortler SJ, Solomonides E, Yampolskaya M . 2018 The isostatic conjecture. (http://arxiv.org/abs/1702.08442) Google Scholar - 10.
Ozkan A, Prabhu R, Baker T, Pence J, Peters J, Sitharam M . 2018 Algorithm 990: efficient atlasing and search of configuration spaces of point-sets constrained by distance intervals.**ACM Trans. Math. Softw.**, 48:1–48:30. (doi:10.1145/3233179) Crossref, Web of Science, Google Scholar**44** - 11.
Jordán T . 2016 Combinatorial rigidity. Graphs and matroids in the theory of rigid frameworks. In*Discrete geometric analysis*(eds MT Barlow, T Jordán, A Zuk), pp. 33–112. Tokyo, Japan: Mathematical Society of Japan. Google Scholar - 12.
Ellenbroek WG, Hagh VF, Kumar A, Thorpe MF, van Hecke M . 2015 Rigidity loss in disordered systems: three scenarios.**Phys. Rev. Lett.**,**114**135501 . (doi:10.1103/PhysRevLett.114.135501) Crossref, PubMed, Web of Science, Google Scholar - 13.
Lester D, Li R . 2018 The frictional pebble game: an algorithm for rigidity percolation in saturated frictional assemblies.**J. Comput. Phys.**, 225–236. (doi:10.1016/j.jcp.2018.05.016) Crossref, Web of Science, Google Scholar**369** - 14.
Henkes S, Quint DA, Fily Y, Schwarz JM . 2016 Rigid cluster decomposition reveals criticality in frictional jamming.**Phys. Rev. Lett.**,**116**028301 . (doi:10.1103/PhysRevLett.116.028301) Crossref, PubMed, Web of Science, Google Scholar - 15.
Maxwell JC . 1864 On the calculation of the equilibrium and stiffness of frames.**Philos. Mag.**, 294–299. (doi:10.1080/14786446408643668) Crossref, Google Scholar**27** - 16.
Asimow L, Roth B . 1978 The rigidity of graphs.**Trans. Am. Math. Soc.**, 279–289. (doi:10.1090/S0002-9947-1978-0511410-9) Crossref, Web of Science, Google Scholar**245** - 17.
Laman G . 1970 On graphs and rigidity of plane skeletal structures.**J. Eng. Math.**, 331–340. (doi:10.1007/BF01534980) Crossref, Web of Science, Google Scholar**4** - 18.
Jacobs DJ, Hendrickson B . 1997 An algorithm for two-dimensional rigidity percolation: the pebble game.**J. Comput. Phys.**, 346–365. (doi:10.1006/jcph.1997.5809) Crossref, Web of Science, Google Scholar**137** - 19.
Berg AR, Jordán T . 2003 Algorithms for graph rigidity and scene analysis. In*Algorithms—ESA 2003*. Lecture Notes in Computer Science, vol. 2832, pp. 78–89. Berlin, Germany: Springer. Google Scholar - 20.
White NL, Whiteley W . 1983 The algebraic geometry of stresses in frameworks.**SIAM J. Algebraic Discrete Methods**, 481–511. (doi:10.1137/0604049) Crossref, Google Scholar**4** - 21.
Connelly R, Terrell M . 1995 Globally rigid symmetric tensegrities [Tenségrités symétriques globalement rigides].*Structural Topology***21**, 59–78. Dual French–English text. See https://upcommons.upc.edu/handle/2099/1099. Google Scholar - 22.
Gabow HN, Westermann HH . 1992 Forests, frames, and games: algorithms for matroid sums and applications.**Algorithmica**, 465–497. (doi:10.1007/BF01758774) Crossref, Web of Science, Google Scholar**7** - 23.
Thurston W . Geometry and topology of three-manifolds. See http://library.msri.org/books/gt3m/. Google Scholar - 24.
Connelly R, Whiteley W . 1996 Second-order rigidity and prestress stability for tensegrity frameworks.**SIAM J. Discrete Math.**, 453–491. (doi:10.1137/S0895480192229236) Crossref, Web of Science, Google Scholar**9** - 25.
Tay TS, Whiteley W . 1984 Recent advances in the generic rigidity of structures.*Structural Topology***9**, 31–38. Dual French–English text. See http://www-iri.upc.es/people/ros/StructuralTopology/ST9/st9-06-a3-ocr.pdf. Google Scholar - 26.
Katoh N, Tanigawa Si . 2011 A proof of the molecular conjecture.**Discrete Comput. Geom.**, 647–700. (doi:10.1007/s00454-011-9348-6) Crossref, Web of Science, Google Scholar**45** - 27.
Lam WY . 2017 Minimal surfaces from infinitesimal deformations of circle packings. (https://arxiv.org/abs/1712.08564) Google Scholar - 28.
Lam WY, Pinkall U . 2017 Isothermic triangulated surfaces.**Math. Ann.**, 165–195. (doi:10.1007/s00208-016-1424-z) Crossref, Web of Science, Google Scholar**368** - 29.
Gluck H . 1975 Almost all simply connected closed surfaces are rigid. In*Geometric topology*(eds LC Glaser, TB Rushing), pp. 225–239. Berlin, Germany: Springer. Google Scholar - 30.
Alexandrov AD . 2005*Convex polyhedra*. Springer Monographs in Mathematics. Berlin, Germany: Springer. Translated from the 1950 Russian edition by N. S. Dairbekov, S. S. Kutateladze and A. B. Sossinsky, With comments and bibliography by V. A. Zalgaller and appendices by L. A. Shor and Yu. A. Volkov. Google Scholar - 31.
Izmestiev I . 2009 Projective background of the infinitesimal rigidity of frameworks.**Geom. Dedicata**, 183–203. (doi:10.1007/s10711-008-9339-9) Crossref, Web of Science, Google Scholar**140** - 32.
Coxeter HSM . 1966 Inversive distance.**Ann. Mat. Pura Appl.**, 73–83. (doi:10.1007/BF02413734) Crossref, Google Scholar**71** - 33.
Bowers JC, Bowers PL, Pratt K . 2018 Almost all circle polyhedra are rigid. (http://arxiv.org/abs/1807.09355) Google Scholar - 34.
Bochnak J, Coste M, Roy MF . 1998*Real algebraic geometry*. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36. Berlin, Germany: Springer. Translated from the 1987 French original; revised by the authors. Google Scholar - 35.
Basu S, Pollack R, Roy MF . 2003*Algorithms in real algebraic geometry*. Algorithms and Computation in Mathematics, vol. 10. Berlin, Germany: Springer. Google Scholar - 36.
Guillemin V, Pollack A . 1974**Differential topology**. Englewood Cliffs, NJ: Prentice-Hall, Inc. Google Scholar - 37.
Guo R . 2011 Local rigidity of inversive distance circle packing.**Trans. Am. Math. Soc.**, 4757–4776. (doi:10.1090/tran/2011-363-09) Crossref, Web of Science, Google Scholar**363** - 38.
Cheng J, Sitharam M, Streinu I . 2009 Nucleation-free 3D rigidity. In*Proc. 21st Annu. Canadian Conf. on Computational Geometry, Vancouver, British Columbia, Canada, 17–19 August 2009*, pp. 71–74. See http://cccg.ca/proceedings/2009/cccg09_19.pdf. Google Scholar - 39.
Rudin W . 1976*Principles of mathematical analysis*. Auckland-Düsseldorf 3rd edition. International Series in Pure and Applied Mathematics. New York, NY: McGraw-Hill Book Co. Google Scholar