4.3 Article

The continuum limit of critical random graphs

Journal

PROBABILITY THEORY AND RELATED FIELDS
Volume 152, Issue 3-4, Pages 367-406

Publisher

SPRINGER HEIDELBERG
DOI: 10.1007/s00440-010-0325-4

Keywords

Random graphs; Gromov-Hausdorff distance; Scaling limits; Continuum random tree; Diameter

Funding

  1. NSERC
  2. EPSRC [EP/D065755/1]
  3. EPSRC [EP/D065755/1, EP/D065755/2] Funding Source: UKRI
  4. Engineering and Physical Sciences Research Council [EP/D065755/1, EP/D065755/2] Funding Source: researchfish

Ask authors/readers for more resources

We consider the ErdAs-R,nyi random graph G(n, p) inside the critical window, that is when p = 1/n + lambda n (-4/3), for some fixed lambda is an element of R. We prove that the sequence of connected components of G(n, p), considered as metric spaces using the graph distance rescaled by n(-1/3), 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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.3
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

Article Statistics & Probability

The Brownian continuum random tree as the unique solution to a fixed point equation

Marie Albenque, Christina Goldschmidt

ELECTRONIC COMMUNICATIONS IN PROBABILITY (2015)

Article Statistics & Probability

A line-breaking construction of the stable trees

Christina Goldschmidt, Benedicte Haas

ELECTRONIC JOURNAL OF PROBABILITY (2015)

Article Statistics & Probability

BEHAVIOR NEAR THE EXTINCTION TIME IN SELF-SIMILAR FRAGMENTATIONS II: FINITE DISLOCATION MEASURES

Christina Goldschmidt, Benedicte Haas

ANNALS OF PROBABILITY (2016)

Article Statistics & Probability

Behavior near the extinction time in self-similar fragmentations I: The stable case

Christina Goldschmidt, Benedicte Haas

ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES (2010)

Article Statistics & Probability

Fragmenting random permutations

Christina Goldschmidt, James B. Martin, Dario Spano

ELECTRONIC COMMUNICATIONS IN PROBABILITY (2008)

Article Statistics & Probability

Asymptotics of the allele frequency spectrum associated with the Bolthausen-Sznitman coalescent

Anne-Laure Basdevant, Christina Goldschmidt

ELECTRONIC JOURNAL OF PROBABILITY (2008)

Article Statistics & Probability

Critical random graphs: limiting constructions and distributional properties

L. Addario-Berry, N. Broutin, C. Goldschmidt

ELECTRONIC JOURNAL OF PROBABILITY (2010)

Article Computer Science, Theory & Methods

Parking on a Random Tree

Christina Goldschmidt, Michal Przykucki

COMBINATORICS PROBABILITY & COMPUTING (2019)

Article Statistics & Probability

Inverting the cut-tree transform

Louigi Addario-Berry, Daphne Dieuleveut, Christina Goldschmidt

ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES (2019)

Article Statistics & Probability

THE SPREAD OF FIRE ON A RANDOM MULTIGRAPH

Christina Goldschmidt, Eleonora Kreacic

ADVANCES IN APPLIED PROBABILITY (2019)

Proceedings Paper Mathematics

Quantum Heisenberg models and their probabilistic representations

Christina Goldschmidt, Daniel Ueltschi, Peter Windridge

ENTROPY AND THE QUANTUM II (2011)

Article Statistics & Probability

Coagulation-fragmentation duality, Poisson-Dirichlet distributions and random recursive trees

Rui Dong, Christina Goldschmidt, James B. Martin

ANNALS OF APPLIED PROBABILITY (2006)

Article Statistics & Probability

Random recursive trees and the Bolthausen-Sznitman coalescent

C Goldschmitd, JB Martin

ELECTRONIC JOURNAL OF PROBABILITY (2005)

Article Statistics & Probability

THE SCALING LIMIT OF THE MINIMUM SPANNING TREE OF THE COMPLETE GRAPH

Louigi Addario-Berry, Nicolas Broutin, Christina Goldschmidt, Gregory Miermont

ANNALS OF PROBABILITY (2017)

No Data Available