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 .
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 metric.
Charles Radin’s Pinwheel tiling is quasi-isometric to Euclidean plane with multiplicative constant which tends to 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 -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 (process christened “Bernoulli bond percolation” in 1953 by Hammersley, working for the mining administration). In 1957, it was shown that there is such that
- if , there is an infinite cluster almost surely;
- if , all clusters are finite.
In two dimensions, and at there is no infinite cluster a.s.
Let , condition on the origin to be in the infinite connected component and look at large balls rescaled to have diameter . They converge to a centrally symmetric convex body, the limiting shape (this fails for ).
Conjecture: As , 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 ?
Answer is no if size is small compared to diameter.
Theorem 1 (Benjamin-Finucane-Tessera) If for some , then some subsequence converges to a torus of dimension .
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 and .
Conjecture: View graphs as electrical networks where each edge has unit resistence. Then
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 is -roughly transitive of for every pair of points , , there is a -quasi-isometry sending to .
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 -sphere ?
Can one realize in ?
Story started with Koebe: All planar graphs admit a circle packing.
Thurston showed that packable graphs have good separators: every finite subgraph of size ca be broken into twicesmaller pieces by removing edges.
4.1. Metrics on graphs from packings
Theorem 3 (Benjamini-Schramm) , Tree cannot be packed in .
Theorem 4 (Benjamini-Curien) A graph with large girth does not pack into for .
Following a suggestion by Gromov, we prove
Theorem 5 (Benjamini-Curien) If has a regular packing in , then the isoperimetric profile of is either linear or .
Question: Show that any packing of in has exactly one accumulation point.