** 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 , be independant realizations. Does tend to 0 ? Bound ?

Side question: say a graph is -roughly transitive if there is a -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) ?

admits one. Exercise: Regular tree does not.

**Theorem 2 (Benjamini-Tessera)** * Positive first -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 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 , start random walk at some vertex and stop when it hits , yielding harmonic measure on .

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

Then, for any set , harmonic measure is supported on a set of size .

** 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 , there is a set of size 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.

### Like this:

Like Loading...

*Related*

## 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
http://www.math.ens.fr/metric2011/