E104-05 - Forschungsbereich Kombinatorik und Algorithmen
-
Journal:
BERNOULLI
-
ISSN:
1350-7265
-
Date (published):
1-Nov-2023
-
Number of Pages:
25
-
Publisher:
INT STATISTICAL INST
-
Peer reviewed:
Yes
-
Keywords:
Local limits; Planar graphs; Random graphs
en
Abstract:
We prove that the random simple connected cubic planar graph Cn with an even number n of vertices admits a novel uniform infinite cubic planar graph (UICPG) as quenched local limit. We describe how the limit may be constructed by a series of random blow-up operations applied to the dual map of the type III Uniform Infinite Planar Triangulation established by Angel and Schramm (Comm. Math. Phys. 24...
We prove that the random simple connected cubic planar graph Cn with an even number n of vertices admits a novel uniform infinite cubic planar graph (UICPG) as quenched local limit. We describe how the limit may be constructed by a series of random blow-up operations applied to the dual map of the type III Uniform Infinite Planar Triangulation established by Angel and Schramm (Comm. Math. Phys. 241 (2003) 191–213). Our main technical lemma is a contiguity relation between Cn and a model where the networks inserted at the links of the largest 3-connected component of Cn are replaced by independent copies of a specific Boltzmann network. We prove that the number of vertices of the largest 3-connected component concentrates at κn for κ ≈ 0.85085, with Airy-type fluctuations of order n2/3. The second-largest component is shown to have significantly smaller size OP n2/3.
en
Research Areas:
Mathematical and Algorithmic Foundations: 95% Computer Science Foundations: 5%