Recurrence of Distributional Limits of Finite Planar Graphs

2001/01/01 by Itaï Benjamini, Oded Schramm · 3 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Stochastic processes and statistical mechanics #Advanced Graph Theory Research #Mathematics #Combinatorics #Subsequence #Vertex (graph theory) #Bounded function #Planar graph #Limit (mathematics) #Discrete mathematics #Random graph #Sequence (biology) #Uniform boundedness #Longest increasing subsequence #Planar #Graph

paper · pdf · doi:10.1214/ejp.v6-96

openalex publication_date 2001/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08

Abstract

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 Packing Theorem. The motivation for this work comes from the theory of random spherical triangulations.

Citations

• On the Angular Resolution of Planar Graphs
• The spectral dimension of 2D quantum gravity
• Coin graphs, Polyhedra, and conformal mapping
• Un principe variationnel pour les empilements de cercles
• Quantum geometry and diffusion

Cited by

• Oded Schramm: From circle packing to SLE
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Circle packing theorem [wikipedia]