Notes of Itai Benjamini’s 2014 lecture

Invariant random structures

1. First passage percolation

Multiply length of edges of the 2-grid by 1 or 10 with equal probabilities. Known : there is an asymptotic shape. What is it ?

UIPT : the limit is not deterministic.

Stationary first passage percolation. On trees (Dekking and Host 1991).

Theorem 1 (Benjamini-Tessera) FPP on vertex transitive graphs of polynomial groth almost surely Gromov-Hausdorff converges after rescaling to a Carnot group.

Convergence to a deterministic metric space works on other groups ? Lamplighter ? Let {X}, {Y} be independant realizations. Does {d_X(o,v_n)/d_Y(o,v_n)} tend to 0 ? Bound {Var(d_X(o,v_n))} ?

Side question: say a graph is {C}-roughly transitive if there is a {C}-quasi-isometry mapping every point to every other point. Does this imply space is quasi-isometric to a homogeneous space ?

2. Partitions

Partition a graph into infinitely many roughly connected infinite subgraphs, each one touching finitely many others. Which Cayley graphs admit invariant random partitions of that sort (i.e. a measure on partitions, invariant under automorphisms) ?

{{\mathbb Z}^2} admits one. Exercise: Regular tree does not.

Theorem 2 (Benjamini-Tessera) Positive first {L^2}-Betti number implies no such invariant random partitions.

Conjecture: Lamplighter does not admit IRP.

2.1. Iterations

Given a random partition, can you random partition again ? Try {{\mathbb Z}\times} tree.

3. Invariant majority dynamics

For odd degree graph, each vertex changes its mind according to majority of its neighbours.

For finite graphs, the process stabilizes in finite time.

Theorem 3 (Benjamini-Tamuz) Start with invariant random opinions. Then almost surely opinions stabilize in finite time (every second time).

4. Harmonic measure

Given a set {S}, start random walk at some vertex and stop when it hits {S}, yielding harmonic measure on {S}.

Let {G_n} be finite, connected, vertextransitive graphs with bounded degree and large diameters,

\displaystyle  \begin{array}{rcl}  |G_n|=o(diam(G_n)^d). \end{array}

Then, for any set {S_n}, harmonic measure is supported on a set of size {o(|G_n|)}.

4.1. Beyond polynomial growth

On expanders, for sets of at most half the size, when averaging over starting vertices, harmonic measure is supported on a set of size proportional to size of the set (with Yadin).

On lamplighter {{\mathbb Z}_2 \wr {\mathbb Z}_n}, there is a set of size {|G|/4} for which harmonic measure is supported on a set of size proportional to size of the set, and other sets where harmonic measure is supported on a small subset.


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 Workshop lecture 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