The continuum limit of critical random graphs

2009/03/27 by Louigi Addario‐Berry, Addario-Berry, Louigi, Nicolas Broutin +3 · 4 citations
Mathematics · #Stochastic processes and statistical mechanics #Limits and Structures in Graph Theory #Geometry and complex manifolds

paper · doi:10.48550/arxiv.0903.4730

Abstract

We consider the Erdos-Renyi random graph G(n,p) inside the critical window, that is when p=1/n+ lambda*n^-4/3, for some fixed lambda in R. Then, as a metric space with the graph distance rescaled by n^-1/3, the sequence of connected components G(n,p) converges towards a sequence of continuous compact metric spaces. The result relies on a bijection between graphs and certain marked random walks, and the theory of continuum random trees. Our result gives access to the answers to a great many questions about distances in critical random graphs. In particular, we deduce that the diameter of G(n,p) rescaled by n^-1/3 converges in distribution to an absolutely continuous random variable with finite mean.

Citations

• Uniform bounds for exponential moment of maximum of a Dyck paths

Cited by

• Percolation on random graphs
• Geometry of critical discrete structures: percolation on the hierarchical lattice
• Critical random graphs: limiting constructions and distributional properties
• Universal diameter bounds for random graphs with given degrees

Related

• Critical random graphs: limiting constructions and distributional properties
• Continuum limit of critical inhomogeneous random graphs
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• The scaling limit of the minimum spanning tree of the complete graph
• The scaling limit of a critical random directed graph