Local limit of sparse random planar graphs

M. Kang, M. Missethan

Research output: Working paperPreprint

Abstract

Let P(n,m) be a graph chosen uniformly at random from the class of all planar graphs on vertex set {1,...,n} with m = m(n) edges. We determine the (Benjamini-Schramm) local weak limit of P(n,m) in the sparse regime when m ≤ n+o 3 n¡logn¢−2/3´. Assuming that the average degree 2m/n tends to a constant c ∈ [0,2] the local weak limit of P(n,m) is a Galton-Watson tree with offspring distribution Po(c) if c ≤ 1, while it is the 'Skeleton tree' if c = 2. Furthermore, there is a 'smooth' transition between these two cases in the sense that the local weak limit of P(n,m) is a 'linear combination' of a Galton-Watson tree and the Skeleton tree if c ∈ (1,2).
Original languageEnglish
Number of pages22
Publication statusPublished - 2021

Fields of Expertise

  • Information, Communication & Computing

Fingerprint

Dive into the research topics of 'Local limit of sparse random planar graphs'. Together they form a unique fingerprint.

Cite this