SCALING LIMITS OF RANDOM GRAPHS FROM SUBCRITICAL CLASSES

• 成果类型: Article
• 署名作者: Panagiotou, Konstantinos; Stufler, Benedikt; Weller, Kerstin
• 署名单位: University of Munich; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/15-AOP1048
• 发表日期: 2016
• 页码: 3291-3334
• 关键词: galton-watson trees; continuum random tree; planar maps; excursions; diameter; THEOREM; height

摘要

We study the uniform random graph C-n with n vertices drawn from a subcritical class of connected graphs. Our main result is that the resealed graph C-n / root n converges to the Brownian continuum random tree T-e multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide sub-Gaussian tail bounds for the diameter D (C-n) and height H(C-n(center dot)) of the rooted random graph C-n(center dot) We give analytic expressions for the scaling factor in several cases, including for example the class of outerplanar graphs. Our methods also enable us to study first passage percolation on C-n, where we also show the convergence to T-e under an appropriate rescaling.