Scaling limits of random graphs from subcritical classes

DOI10.1214/15-AOP1048MaRDI QIDQ341486zbMATH OpenOpenAlexFDO

Authors Benedikt Stufler, Kerstin Weller, Konstantinos Panagiotou

Publication date 16 November 2016

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1865, https://projecteuclid.org/euclid.aop/1474462098

zbMATH Keywords

continuum random treefirst passage percolationrandom graphsscaling limitssubcritical graph classes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Functional limit theorems; invariance principles (60F17) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study the uniform random graph $mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $mathsf{C}_n/sqrtn$ converges to the Brownian Continuum Random Tree $mathcal{T}_{mathsfe}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $extD(mathsf{C}_n)$ and height $$ of the rooted random graph $$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on $mathsf{C}_n$, where we show the convergence to $mathcal{T}_{mathsfe}$ under an appropriate rescaling.

Recommendations

• Scaling limits of random graphs from subcritical classes: extended abstract
• Scaling limits of random trees and graphs
• Asymptotic study of subcritical graph classes
• The degree sequence of random graphs from subcritical classes
• The continuum limit of critical random graphs

Cited in

(45)

• Excursion theory for Brownian motion indexed by the Brownian tree
• Random enriched trees with applications to random graphs
• Asymptotics of integrals of Betti numbers for random simplicial complex processes
• Self-similar real trees defined as fixed points and their geometric properties
• Universal height and width bounds for random trees
• Enumeration of chordal planar graphs and maps
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• Limits of random tree-like discrete structures
• The boundary of random planar maps via looptrees
• Invariance principles for random walks in random environment on trees
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Scaling limits of random Pólya trees
• Limit laws for UGROW random graphs
• Asymptotic properties of random unlabelled block-weighted graphs
• Local convergence of random planar graphs
• Scaling limits of random graphs from subcritical classes: extended abstract
• Scaling limits of random trees and random graphs
• Scaling limit for the random walk on the largest connected component of the critical random graph
• Subcritical graph classes containing all planar graphs
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Graph limits of random graphs from a subset of connected k-trees
• On local weak limit and subgraph counts for sparse random graphs
• A branching process approach to level‐k phylogenetic networks
• On breadth‐first constructions of scaling limits of random graphs and random unicellular maps
• Exact-Size Sampling of Enriched Trees in Linear Time
• Random cographs: Brownian graphon limit and asymptotic degree distribution
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• A phase transition in block-weighted random maps
• Asymptotic enumeration and limit laws for multisets: the subexponential case
• First-passage percolation on random simple triangulations
• Random cubic planar graphs converge to the Brownian sphere
• Scaling Limits of Markov-Branching Trees and Applications
• On random trees and forests
• Chordal graphs with bounded tree-width
• Random trees have height \(O(\sqrt{n})\)
• The scaling limit of random cubic planar graphs
• Continuum limit of critical inhomogeneous random graphs
• Scaling limit of graph classes through split decomposition
• Chordal graphs with bounded tree-width (extended abstract)
• Limits of chordal graphs with bounded tree-width
• Subgraph densities and scaling limits of random graphs with a prescribed modular decomposition
• Probabilistic enumeration and equivalence of nonisomorphic trees
• Dense and nondense limits for uniform random intersection graphs
• The scaling limit of random two-connected series-parallel maps
• Random graphs from a block-stable class

This page was built for publication: Scaling limits of random graphs from subcritical classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q341486)