Percolation

Lecture V
Session on Granular Matter
Institut Henri Poincaré
R. Connelly
Cornell University
Department of Mathematics

1
What is Percolation?

2
 What is Percolation?
• A classic example: Immerse a large stone in a
bucket of water. What it probability that the
center of the stone is wetted?
• In the plane, model the stone as a square lattice,
and declare each edge to be open with probability
p > 0.
• There is a critical probability pc such that for p >pc
a point in the middle is connected to the outside
with high probability, and for p<pc it isn’t.
3
 Rigidity Percolation
Start with a planar triangular lattice. Leave
each edge with probability p > 0. As a
generic bar-and-joint framework, what is
the probability that two vertices will be in
the same rigid component? Is there a
critical probability pc as in the classical
case?

4
 Tension Percolation
Start with the planar triangular lattice, clamp
the boundary and again leave in an edge
with probability p. But now regard the
graph as having all cables, with pinned
vertices on the boundary, a kind of spider
web. Is there critical probability pc <1 as
before?
But first some basics.
5
 Generic configurations
A configuration p is called generic if the coordinates
of all of its points are algebraically independent
over the rational numbers. In other words, any
non-zero polynomial with rational coefficients
will not vanish when the variables are replaced by
the coordinates of p.
For example, p, e, g, … are algebraically
independent.

6
 Generic rigidity
Theorem: If a bar framework is rigid at one generic
configuration then it is infinitesimally rigid at all
generic configurations. If it is infinitesimally rigid
at some, possibly non-generic, configuration, then
it is infinitesimally rigid at all generic
configurations.
This means that generic rigidity is a combinatorial
property of the graph G only.
Theorem (Laman 1972): Suppose that G has n
vertices and e = 2n-3 edges. Then G is generically
rigid in the plane if and only if for every subgraph
of G with n¢ vertices and e¢ edges e¢ £ 2n¢-3.
7
 Algorithms
Corollary (Sugihara 1979, Lovász and Yemini 1982): Given a
graph G with n vertices and e edges, there is an algorithm to
determine whether G is generically rigid in the plane in at
most O(ne) steps. (Variations: 2-tree condition, the pebble
game, etc.) For the following description, see Jacobs and
Hendrickson 1997.
In both cases 9 = e = 2n-3 = 2*6-3.

Generically rigid Not generically rigid

8
The pebble game

Start with 2 pebbles

assigned to each vertex.

9
 The pebble game

Then try to assign each pebble to an

adjacent edge, but do not assign
more than one pebble to each edge.

10
The pebble game
If all edges are covered by
pebbles from adjacent vertices,
this is a certificate that Laman's
condition holds and the graph is
generically rigid in the plane.

If there are more than 3 pebbles left,

backtrack along other edges until
there is an edge without a pebble.

11
 Rigidity Percolation
This is a suggested model for the onset of rigidity in glasses.
Start with the following bar framework, each bar is retained with a certain
probability p.

12
 Rigidity Percolation
Start with the following bar framework, each bar is retained with a certain
probability p. Imagine perturbing the configuration so that the
configuration is generic, and then apply the pebble game algorithm to
compute rigidity.

13
 Rigidity Percolation
Start with the following bar framework, each bar is retained with a certain
probability p. Imagine perturbing the configuration so that the
configuration is generic, and then apply the pebble game algorithm to
compute rigidity. The critical probability p where the framework
becomes non-rigid is the rigidity percolation threshold.

14
 Average degree
If a graph G has n vertices and e edges, let ni be the number
of vertices of degree i. Then
Si ini = 2e,
define (Si ini)/ Si ni = (Si ini)/n = 2e/n = Z as the average
degree or coordination number. If G represents the bars of
a generically rigid bar framework in the plane, then e ≥
2n-3, and so Z ≥ 4 - 6/n.
So in the percolation problem, the graph cannot be rigid until
p ≥ 2/3, and indeed the “floppy modes” do not decrease
until a critical percolation at about p = 0.6603. (Thorpe,
Duxbury, etc. 1990’s)

15
16
 Tension Percolation
Spider Webs: Consider any tensegrity framework
G(p) with all member cables and some pinned
vertices, called a spider web. When is it rigid?

Pinned vertices in black.

17
 Tension Percolation
Theorem: If a spider web has a proper self stress,
strictly positive on all cables all connected to a
pinned vertex, then it is rigid (in any dimension).
Pinned
Pinned

Note that this framework This spider web will be have a

is NOT infinitesimally rigid self stress and be rigid if and
since it has 3 non-pinned only if the 3 outside cables lie
vertices and only 6 cables. on lines that meet at a point.

Pinned

18
 Spider proof
Let w=(…,wij,…) be the proper self stress, non-zero
on all the cables at the configuration p. For each
configuration q, define the energy function:
E(q)= Si<j wij|qi - qj|2.
Note that E is a quadratic function, and that since
E(q)= wR(q)q, we have that p is a critical point
for E, since wR(p) =0. Since each wij >0, p is
clearly a minimum. If q is another minimum point
for E, then E((1-t)q+tp), for t real, would also be a
minimum, which is not possible, since cables
would be stretched to infinity. //

19
Tension Percolation

A cable framework in the plane with the boundary vertices pinned.

Internal bars are deleted with a certain probability p.

How can you tell easily when it has a positive self stress?

20
 Remark about packings
Recall that by the Roth-Whiteley criterion,
this same stress condition, but with the
opposite sign, relates to to packings of
circles in a triangular lattice. Can you
randomly delete (1-p) of the contacts and
hope to have a self stress, all negative on all
the struts?

21
 The final stress

With the sum of these stresses, each of 1 unit in each cable, every vertex
has an incident cable with a positive self stress and so this is rigid.

22
 The critical probability
Take the triangular lattice, and for each edge
independently decide to keep each edge
with probability p. Is there a critical
probability pc < 1 that determines a
transition from having a stress to not having
a stress?

23
 The critical probability
Take the triangular lattice, and for each edge
independently decide to keep each edge with
probability p. Is there a critical probability pc < 1
that determines a transition from having a stress to
not having a stress?
Answer: No. For a large enough lattice, and for any
p < 1, the network will lose tension.
Connelly, Robert(1-CRNL); Rybnikov, Konstantin(1-CRNL); Volkov, Stanislav(4-BRST)
Percolation of the loss of tension in an infinite triangular lattice. (English. English summary)
J. Statist. Phys. 105 (2001), no. 1-2, 143--171.

24
 Eliminating edges
There are instances when one can show that the
stresses in many members is 0.
After the cables have been chosen, we can
eliminate more as in the dark edges below.

25
 Nuances

Some configurations are subtle. This is an example, where each

vertex can be locally in equilibrium with positive stresses, but
the stress on the red cables must be 0.

26
The idea of the proof

Look inside ever larger hexagons, and argue inductively

that by using the unnuanced process for eliminating
edges that the interior edges have 0 stress. Then with
high probability, each of the edges of the hexagon have
an edge that is missing. This eliminates the next layer.

27
 Calculating the probabilities
Suppose that a hexagon with m edges on a
side has stresses all 0 inside. Then the
probability that at least one edge from each
of the 6 sides will have been deleted, and
hence creating an empty hexagon with m+1
sides, is (1-pm)6. So the probability that this
will continue to infinity is Pm•(1-pn)6. For
fixed p<1 and m -> • this tends to 1.//
28
 A continuous model
Imagine the plane as a piece of paper clamped
outside a large convex polygon. Cut out holes in
the paper.
• Can the paper be folded in such a way that it can
be flexed up into space?
• Is there a critical probability such that when the
area of the holes have a small density, then it
cannot be folded?

29
 A continuous model
Imagine the plane as a piece of paper clamped
outside a large convex polygon. Cut out holes in
the paper.
• Can the paper be folded in such a way that it can
be flexed up into space?
• Is there a critical probability such that when the
area of the holes have a small density, then it
cannot be folded?
As before, no, by a similar argument!

30
An example that can be folded

31
 An example that cannot be
folded: an underlying spider web

If there is a triangulation of the complement of the holes

(in purple here) such that there is a positive equilibrium
stress on each edge, then the paper cannot be folded to
flex.

32
 Graphical Statics
In the 19th century a method of computing forces graphically,
as above, was common. And James Clerk Maxwell and
Luigi Cremona showed that there is a visual
correspondence between polyhedral surfaces and the
equilibrium forces in a tensegrity as below.

(Convex) Polyhedral Surface

Stressed Spiderweb

33
 Lifting holes
• If a system of holes can be lifted to a convex
surface with each hole as a convex face, the
Maxwell-Cremona correspondence provides a
stress from the convex hull of the lifted holes to a
spider web in the plane.
• The existence of the lift can be determined by a
linear programming feasibility algorithm.

34