Notes of Itai Benjamini’s lecture nr 2

Today we study a series of examples of random perturbations of homogeneous spaces. Typically, the perturbation depends one one real parameter. When the parameter reaches a critical value, the spaces obtained are more exotic.

1. Variants of percolation

1.1. First passage percolation

Assign independently identically distributed lengths to edges of a graph.

Theorem 1 (Richardson) For the {{\mathbb Z}^d} grid, for exponentially distributed lengths, large balls converge to a deterministic convex centrally symmetric shape.

Simulation indicates, and Kesten proved in high dimensions, that the limiting shape is not round. It is distribution dependent. It can have flat parts.


  1. How do geodesics between two point behave ? In high dimensions, they should be concentrated along a line.
  2. Variance {\sim n^{2/3}} ? Known : variance {\leq \frac{n}{\log n}}.
  3. How do geodesic rays behave ?
  4. (Furstenberg). No two sided infinite geodesics ?

Very few results for {{\mathbb Z}^d}. Only trees are well understood.

1.2. Long range percolation

The random metric performs some averaging, so the perturbation is mild. Next we study stronger perturbation, where the underlying Euclidean geometry does not fully disappear, but fades away.

Definition 2 Start with {n}-cycle. Add an edge between {i} and {j} with probability {\beta|i-j|^{-s}}.

{s>2} does not change geometry much, diameter stays linear in {n}.

{s=2} is the critical case, see below.

{1<s<2} (Biskup), diameter is polylog.

{s=1} (Coppersmith, Gamarnik, Sviridenko) diameter is {\frac{\log n}{\log\log n}}.

{s<1} diameter is bounded.

Theorem 3 (Sly and Ding 2012) When {s=2}, diameter is {\theta(n^{f(\beta)})}, where {f} is strictly between 0 and 1.

Not even clear whether {f} is increasing, or continuous.

These random graphs look very different from vertex transitive graphs. Even in the subcritical case, {1<s<2}, the mixing time of the simple random walk is {n^{s-1}}. Plenty of bottlenecks. Critical case even worse.

1.3. CCCP

CCCP means Contracting clusters in critical percolation.

One contracts each cluster in a bond percolation on {{\mathbb Z}^d}. For {p<p_c}, this is probably quasi-isometric to {{\mathbb Z}^d}. But for {p=p_c}, it looks different. Locally, vertices have high degrees. Volume growth is huge (Benjamini-Gurel-Gurevich-Kosma), but no non constant bounded harmonic functions.

2. Random planar graphs

Motivated by quantum gravity.

2.1. Random subdivisions

Toy model: Start with the unit square, divide it in 4 squares, pick one at random and divide it, and iterate.

Conjecture. Diameter (minimal number of squares in a chain) grows at a deterministic speed.

This would imply that the limiting random planar length space is non trivial.

2.2. Stationary graphs

Analogue of stationary processes. Weakening of vertex transitivity.

Definition 4 A distribution on rooted graphs is stationary if invariant under re-rooting at the points of a simple random walk path.

Sample have polynomial volume growth, some examples have superquadratic volume growth. I.e. full of mushrooms. Nevertheless,

Theorem 5 (Benjamini-Papasoglu) Any doubling planar graph has linear size cuts at all scales, i.e. for all {n}, there is a plane domain, squeezed between {B(o,n)} and {B(o,6n)}, with linear boundary length.

Conjecture. On such graphs, random walk is sub-diffusive. Indeed, it will probably get trapped in the deep mushrooms.

3. Local convergence

Definition 6 A random rooted graph {G} is the local limit of a sequence of random finite graphs

Example 1 {G_n=} binary tree of depth {n}.

Since a random vertex is close to the leaves, the limit is the canopy tree: a half-line with a bush of depth {n} at vertex {n}, and a distribution on roots.

Theorem 7 (Benjamini-Schramm) Limits of bounded degree finite planar graphs are almost surely recurrent.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s