Recurrence of Distributional Limits of Finite Planar Graphs

By Itai Benjamini, Oded Schramm. 2000

747 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/d8384b98b21d7990c2ed7738e04f790ff6152d55

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Mathematical Physics

Citations in the corpus

Percolation on uniform infinite planar maps (2013, background): “In this paper, rather than dealing with continuous scaling limits, we consider local limits of random maps as introduced in [8], which is a natural way to construct random infinite planar graphs.”
Asymptotic behavior and distributional limits of preferential attachment graphs (2014, methodology): “Such a vertex does not change the notion of convergence introduced by Benjamini and Schramm; however, the number of homomorphisms from a star with 3 legs into this graph sequence grows like n3/2, implying that the homomorphism density diverges.”
On the growth of $L^2$-invariants for sequences of lattices in Lie groups (2012, background): “As in the introduction, we say a sequence of X-orbifolds Benjamini– Schramm converges to X when (3.3.1) holds for all R.”
A view from infinity of the uniform infinite planar quadrangulation (2012, methodology): “However the lack of a bounded degree property for the UIPQ prevents one from deducing recurrence from these results (see also [7]).”
Some topics in the dynamics of group actions on rooted trees (2011, background): “Although this is not mentioned in [27], it is expedient to identify (Γn, v) and (Γn, w) if they are isomorphic as rooted graphs.”
The local weak limit of the minimum spanning tree of the complete graph (2013, neutral): “For unweighted graphs, such convergence was introduced by Benjamini and Schramm [9].”
Action convergence of operators and graphs (2018, background): “It turns out that for a bounded degree sequence of graphs { G i } ∞ i = 1 the P -operator convergence of the sequence { A ( G i )} ∞ i = 1 is equivalent to local-global convergence (and thus it implies Benjamini–Schramm convergence).”
An $L^{p}$ theory of sparse graph convergence II: LD convergence, quotients and right convergence (2014, background): “But it is easy to check that the 4-cycle has different free energies from a 6-cycle, implying that Gn does not have convergent free energies, and hence does not have convergent microcanonical free energies either (an alternative proof was given in [4], where it was used that Gn does not converge in ”
Processes on Unimodular Random Networks (2006, methodology): “For a few recent examples, see Benjamini and Schramm (2001a), Holroyd and Peres (2003), or Timár (2004).”
Schreier graphs of the Basilica group (2009, background): “Moreover, if we choose the root of Γn uniformly at random for all n ≥ 1, then the uniform measure on the set {(Γξ, ξ); ξ ∈ ∂T } is the random weak limit (in the sense of [4]) of this sequence of random rooted graphs.”
Unimodular random trees (2012, methodology): “It is easy to see that every sofic measure is unimodular, as observed by Benjamini and Schramm [10], who introduced this general form of the mass-transport principle under the name ‘intrinsic mass-transport principle’.”
On exchangeable random variables and the statistics of large graphs and hypergraphs (2008, methodology): “Perhaps the simplest instance of the extraction of a limit object as a measure defined directly on a space of isomorphism classes of infinite models occurs in the work on limit objects for various classes of sparse rooted graph (see, in particular, the papers of Aldous and Steele [5], Aldous and Lyo”
Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs (2018, background): “The established convergence implies convergence for the local weak topology of Benjamini and Schramm (see [3]).”
Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing (2007, methodology): “Convergence of graph sequences was defined by Benjamini and Schramm [8] for graphs with bounded degree.”