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 language | English |
---|---|
Number of pages | 22 |
Publication status | Published - 2021 |
Fields of Expertise
- Information, Communication & Computing