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