## 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.