Notes of Itai Benjamini’s lecture nr 1

The Graphs and Groups workshop consists of 3 mini-courses: Benjamini, Linial, Yu.

On graph limits and random metric spaces

In 1921 Polya observed that a drunken man finds its way back home, but a drunken bird does not. This started the geometric theory of random walks.

How well can the graph metric on bounded degree graphs approximate the metric of homogeneous manifolds ?

1. Slack isometry

This is quasi-isometry with multiplicative constant {1}.

Question: Is there a bounded degree graph which is slack-isometric to Euclidean plane ?

Note that the square grid is slack-isometric to the plan with {L^1} metric.

Charles Radin’s Pinwheel tiling is quasi-isometric to Euclidean plane with multiplicative constant which tends to {1} uniformly in the distance.

The Poisson-Voronoi tessallation (Voronoi cells of a Poisson sample) have an asymptotically Euclidean metric, almost surely. Question: What if one takes Vornoi cells with respect to {L^1}-metric ?

1.1. Near critical percolation

Note that Euclidean metric in built in previous examples. Can one see Euclidean metric arising naturally ?

Start with square grid, remove edges independently at random, with probably {q=1-p} (process christened “Bernoulli bond percolation” in 1953 by Hammersley, working for the mining administration). In 1957, it was shown that there is {0<p_c<1} such that

  1. if {p>p_c}, there is an infinite cluster almost surely;
  2. if {p<p_c}, all clusters are finite.

In two dimensions, {p_c=\frac{1}{2}} and at {p=\frac{1}{2}} there is no infinite cluster a.s.

Let {q<\frac{1}{2}}, condition on the origin to be in the infinite connected component and look at large balls rescaled to have diameter {1}. They converge to a centrally symmetric convex body, the limiting shape (this fails for {q=\frac{1}{2}}).

Conjecture: As {q\rightarrow\frac{1}{2}}, the limiting shape converges to an Euclidean ball.

It seems to be very hard. The ideas around conformal invariance do not seem to help.

2. Symmetric graphs

We mean vertex transitive graphs.

Question: Is there a sequence of vertex transitive graphs which Gromov-Hausdorff converges to a homogeneous metric on {S^2} ?

Answer is no if size is small compared to diameter.

Theorem 1 (Benjamin-Finucane-Tessera) If {|G_n|=o(diameter(G_n)^d)} for some {d\geq0}, then some subsequence converges to a torus of dimension {<d}.

Proof relies on a recent quantitative version of Gromov’s polynomial growth theorem due to Breuillard, Green and Tao.

The present result is weak, we expect more quantitative versions to have applications to random walks an dpercolation on vertex transitive graphs.

Recall Varopoulos’ result (relying on Gromov): The only Cayley graphs with finite electric resistence are {{\mathbb Z}} and {{\mathbb Z}^2}.

Conjecture: View graphs as electrical networks where each edge has unit resistence. Then

\displaystyle  \begin{array}{rcl}  \textrm{electric resistence}\leq C_d +\frac{diameter(G)^2 log|G|}{diameter(G)}. \end{array}

2.1. Graph closest to the round 2-sphere

The theorem implies existence of a finite vertex-transitive graph which is closest to the round 2-sphere. Is this the truncated icosahedron (soccer ball) ?

3. Roughly transitive graph

Definition 2 Si a space {X} is {(C,c)}-roughly transitive of for every pair of points {x}, {y\in X}, there is a {(C,c)}-quasi-isometry sending {x} to {y}.

Example 1 Broken comb: remove each tooth independently at random. This is roughly transitive.

Question: Do there exist genuine examples, i.e. spaces which are not Hausdorff close to homogeneous spaces ?

4. Opposite direction

Question: Which graphs can be realized as the nerve graph of a sphere packig in Euclidean {d}-sphere ?

Can one realize {{\mathbb Z}^4} in {{\mathbb R}^3} ?

Story started with Koebe: All planar graphs admit a circle packing.

Thurston showed that packable graphs have good separators: every finite subgraph of size {n} ca be broken into twicesmaller pieces by removing {n^{(d-1)/d}} edges.

4.1. Metrics on graphs from packings

Theorem 3 (Benjamini-Schramm) {{\mathbb Z}^4}, Tree{\times{\mathbb Z}} cannot be packed in {{\mathbb R}^3}.

Theorem 4 (Benjamini-Curien) A graph with large girth {g(G)\geq g} does not pack into {{\mathbb R}^d} for {d|\geq d(g(G))}.

Following a suggestion by Gromov, we prove

Theorem 5 (Benjamini-Curien) If {G} has a regular packing in {{\mathbb R}^d}, then the isoperimetric profile of {G} is either linear or {< t^{(d-1)/d}}.

Question: Show that any packing of {{\mathbb Z}^3} in {S^3} has exactly one accumulation point.


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