# Recurrence of Distributional Limits of Finite Planar Graphs

@article{Benjamini2000RecurrenceOD, title={Recurrence of Distributional Limits of Finite Planar Graphs}, author={Itai Benjamini and Oded Schramm}, journal={Electronic Journal of Probability}, year={2000}, volume={6}, pages={1-13} }

Suppose that $G_j$ is a sequence of finite connected planar graphs, and in each $G_j$ a special vertex, called the root, is chosen randomly-uniformly. We introduce the notion of a distributional limit $G$ of such graphs. Assume that the vertex degrees of the vertices in $G_j$ are bounded, and the bound does not depend on $j$. Then after passing to a subsequence, the limit exists, and is a random rooted graph $G$. We prove that with probability one $G$ is recurrent. The proof involves the Circle… Expand

#### Figures from this paper

#### 376 Citations

The Local Limit of the Uniform Spanning Tree on Dense Graphs

- Mathematics, Physics
- 2017

Let G be a connected graph in which almost all vertices have linear degrees and let $$\mathcal {T}$$T be a uniform spanning tree of G. For any fixed rooted tree F of height r we compute the… Expand

Recurrence of planar graph limits

- Mathematics
- 2012

We prove that any distributional limit of finite planar graphs in which the degree of the root has an exponential tail is almost surely recurrent. As a corollary, we obtain that the uniform infinite… Expand

On limits of sparse random graphs

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2016

A notion of convergence for sequences of finite graphs { G n} that can be seen as a generalization of the Benjamini-Schramm convergence notion for bounded degree graphs and the left-convergence notion for dense graphs is presented. Expand

On the structure of random graphs with constant $r$-balls

- Mathematics
- 2018

We continue the study of the properties of graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to the ball of radius $r$ in some fixed vertex-transitive graph $F$,… Expand

Hyperfinite graph limits

- Mathematics
- 2007

G\'abor Elek introduced the notion of a hyperfinite graph family: a collection of graphs is hypefinite if for every $\epsilon>0$ there is some finite $k$ such that each graph $G$ in the collection… Expand

On the local geometry of graphs in terms of their spectra

- Mathematics, Computer Science
- Eur. J. Comb.
- 2019

It is proved that a sequence of graphs that share a common universal cover T and such that the proportion of eigenvalues of G n that lie within the support of the spectrum of T tends to 1 in the large n limit is asymptotically locally tree-like. Expand

Conformal growth rates and spectral geometry on distributional limits of graphs

- Mathematics
- 2017

For a unimodular random graph $(G,\rho)$, we consider deformations of its intrinsic path metric by a (random) weighting of its vertices. This leads to the notion of the {\em conformal growth exponent… Expand

Percolation on Hyperbolic Graphs

- Mathematics, Physics
- Geometric and Functional Analysis
- 2019

We prove that Bernoulli bond percolation on any nonamenable, Gromov hyperbolic, quasi-transitive graph has a phase in which there are infinitely many infinite clusters, verifying a well-known… Expand

Local limits of spatial inhomogeneous random graphs

- Mathematics
- 2021

Consider a set of n vertices, where each vertex has a location in R that is sampled uniformly from the unit cube in R, and a weight associated to it. Construct a random graph by placing edges… Expand

On large-girth regular graphs and random processes on trees

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2018

Using Glauber dynamics on processes to give a sufficient condition for a branching Markov chain to be factor of i.i.d. processes, this work proves a family of combinatorial statements about random $d-regular graphs. Expand

#### References

SHOWING 1-10 OF 31 REFERENCES

Harmonic functions on planar and almost planar graphs and manifolds, via circle packings

- Mathematics
- 1996

Abstract.The circle packing theorem is used to show that on any bounded valence transient planar graph there exists a non constant, harmonic, bounded, Dirichlet function. If
$P$ is a bounded circle… Expand

Group-invariant Percolation on Graphs

- Mathematics
- 1999

Abstract. Let G be a closed group of automorphisms of a graph X. We relate geometric properties of G and X, such as amenability and unimodularity, to properties of G-invariant percolation processes… Expand

On the Cover Time of Planar Graphs

- Mathematics
- 2000

The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any $n$-vertex,… Expand

The growth rate of vertex-transitive planar graphs

- Mathematics, Computer Science
- SODA '97
- 1997

It is shown that the rate of growth of a graph with these properties is either linear or quadratic or exponential, and the same result holds more generally for locally finite, almost vertextransitive planar graphs. Expand

The Distribution of the Maximum Vertex Degree in Random Planar Maps

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2000

We determine the limiting distribution of the maximum vertex degree ?n in a random triangulation of an n-gon, and show that it is the same as that of the maximum of n independent identically… Expand

Random sampling of large planar maps and convex polyhedra

- Mathematics, Computer Science
- STOC '99
- 1999

A versatile almost uniform random generator for planar embeddings of graphs (usually called maps) that applies efficiently to a much wider class of planar graphs than previously known methods. Expand

Infinite clusters in dependent automorphism invariant percolation on trees

- Mathematics
- 1997

We study dependent bond percolation on the homogeneous tree T n of order n ≥ 2 under the assumption of automorphism invariance. Excluding a trivial case, we find that the number of infinite clusters… Expand

Hyperbolic and parabolic packings

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1995

A new proof that ifG is CP hyperbolic andD is any simply connected proper subdomain of the plane, then there is a disk packingP with contacts graphG such thatP is contained and locally finite inD. Expand

Surveys in Combinatorics, 1999: Recent Excluded Minor Theorems for Graphs

- Mathematics
- 1999

A graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. An excluded minor theorem describes the structure of graphs with no minor isomorphic to… Expand

A recurrence/transience result for circle packings

- Mathematics
- 1998

It is known that any infinite simplicial complex homeomorphic to the plane and satisfying a couple of other conditions is the nerve of a circle packing of either the plane or the disc (and not of… Expand