Notes of Itai Benjamini’s lecture nr 3

1. Local limits, continued

1.1. Random triangulations of higher genus surfaces

Guth, Parlier and Young 2010: Glue {N} triangles along sides in order to get surfaces. Use uniform distribution on such data. They give bounds on the size (max length of a curve, total length) of pants decompositions.

Their work indicates that the injectivity radius around a typical tends to infinity.

Earlier work by Gamburd and Makover (2002) shows that the genus grows like {\frac{N}{4}}. It follows that degree is unbounded. This is unfortunate, therefore we modify the model: condition on the genus be equal to {CN} for some {C<\frac{1}{4}}.

Conjecture. This random surface converges to a rooted random triangulation of hyperbolic plane with average degree {\frac{6}{1-4C}}.

1.2. UIPQ

UIPQ, the uniform infinite planar quadrangulation, is

Ph. Chassaing showed that UIPQ can be constructed from a labeled critical Galton-Watson family tree conditioned to survive.

Conjecture. Go to the supercritical Galton-Watson tree. This describes the limit of random finite quadrangulations of surfaces with genus

2. Connective constants for self avoiding walks

Definition 1 Fix a graph {G}. {SAW(n)} is the uniform distribution on all self-avoiding paths of length {n} from a fixed root.

Note it is not easy to simulate. Now, people know how to do it properly for {{\mathbb Z}^d}.

By submultiplicativity, the following limit exists

Definition 2 The connective constant of the graph is

\displaystyle  \begin{array}{rcl}  \mu=\lim_{n\rightarrow\infty}\sqrt[n]{|SAW(n)|}. \end{array}

Theorem 3 (Duminil-Smirnov) For hexagonal planar lattice, {\mu=\sqrt{2+\sqrt{2}}}.

Conjecture. There is a lower bound {>1} for all connective constants of vertex transitive graphs excluding {{\mathbb Z}}. Maybe this lower bound is {\sqrt{2}}, achieved by the ladder.

Possible approach: Treat graphs with large girth, show every graph covers a graph with large girth.

Stronger conjecture. {\mu} is continuous with respect to local convergence for vertex transitive graphs.

G. Kozma showed that the set of connective constants of groups contains an interval. He conjectures that, for planar Cayley graphs, {\mu} is algebraic.

3. Scale invariance

3.1. Expanders at all scales

Question. Does there exists a family of finite {d}-regular graphs {G_n} such that all balls in all {G_n} are uniform expanders ?

This is the opposite of having large girth. It sounds like asking for self-similarity and expansion simultaneously, this is impossible (the model for self-similarity is a torus, which is not an expander). Therefore I believe such objects can’t exist.

Possible approach: via percolation. Since all balls are well connected, there must be a unique giant cluster.

Question. Let {G} be a bounded degree expander, further assume that there is a fixed vertex {v \in G}, such that after performing {p = \frac{1}{2}} percolation
on {G}, the diameter of the component of {v} is {>\frac{1}{2}}diameter{(G)} with probability {>\frac{1}{2}}. Show that there is a giant component with high probability ({G} is not assumed to
be vertex transitive).

3.2. Expander balls

Nati Linial asked for which graphs {H} there exist finite simplicial 2-complexes with {H} as links. Similar question: for which rooted graphs {H} does there exist finite graphs with {H} as {r}-balls ?

Example 1 A 3-ball in the grand-parent graph does not appear as a ball in a finite vertex transitive graph.

When this is the case, a second question arises. Question. What is the minimal diameter of a graph with {H} as {r}-balls ? Give bounds. Can this grow faster than linearly in {r} ?

When {H} is the {r}-ball in a {d}-regular tree, this is the girth problem advertised by Linial.

It sounds like a quantitative version of soficity. For a group, soficity means that balls weakly look like balls in a finite group.

Here is an easier

Question. Take a planar tiling all of whose tiles have diameter {\leq r}. Assume that

3.3. Percolation on groups

I continue with percolation, since this is my approach to non existence of expanders at all scales.

Recall {p_c} and {p_u} are the critical probabilities where transitions between the following events occur.

  1. No infinite cluster.
  2. At least one infinite cluster.
  3. A unique infinite cluster.

For Cayley groups, {p_c} and {p_u} may depend on choice of generating set.

Questions. For which groups is {p_c <1} ? {p_c <p_u} ? Is the property {p_c <p_u} quasi-isometry invariant ?

There is a well developed theory. For {p_c <1}, there are separate results for polynomial growth, Grigorchuk groups, but no uniform argument. {p_c=p_u} for amenable groups. For non-amenable groups, Nagnibeda and Pak (building upon Benjamini and Schramm) showed {p_c <p_u} for suitable generating systems. This has a nice application to the measurable von Neumann problem (Gaboriau-Lyons).


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