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

first passage percolationrandom graphsscaling limitscontinuum random treesubcritical graph classes

Mathematics Subject Classification ID

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

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

(38)

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

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)