The continuum limit of critical random graphs

DOI10.1007/s00440-010-0325-4zbMath1239.05165MaRDI QIDQ2428503

Louigi Addario-Berry, Nicolas Broutin, Christina Goldschmidt

Publication date: 26 April 2012

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00440-010-0325-4

zbMATH Keywords

random walks; random graphs; diameter; Gromov-Hausdorff distance; bijection; scaling limits; continuum random tree; distances in critical random graphs

Mathematics Subject Classification ID

05C05: Trees

05C35: Extremal problems in graph theory

05C80: Random graphs (graph-theoretic aspects)

60C05: Combinatorial probability

05C12: Distance in graphs

05C81: Random walks on graphs

Related Items

Critical random forests, Asymptotics of trees with a prescribed degree sequence and applications, A new encoding of coalescent processes: applications to the additive and multiplicative cases, Scaling limit for the random walk on the largest connected component of the critical random graph, The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs, Scaling limits and influence of the seed graph in preferential attachment trees, The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs, Continuum limit of critical inhomogeneous random graphs, The hyperbolic Brownian plane, Critical random graphs and the differential equations technique, Tail bounds for the height and width of a random tree with a given degree sequence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Critical random graphs: limiting constructions and distributional properties
• Depth-first search as a combinatorial correspondence
• The continuum random tree. I
• Critical random graphs: Diameter and mixing time
• The critical random graph, with martingales
• Random trees and applications
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• Uniform bounds for exponential moment of maximum of a Dyck path
• The average height of binary trees and other simple trees
• Brownian excursions, critical random graphs and the multiplicative coalescent
• The depth first processes of Galton-Watson trees converge to the same Brownian excursion
• On the largest component of the random graph at a nearcritical stage
• The continuum random tree. III
• Probability and real trees. Ecole d'Eté de Probabilités de Saint-Flour XXXV -- 2005. Lecture given at the Saint-Flour probability summer school, July 6--23, 2005.
• Random real trees
• Critical random hypergraphs: the emergence of a giant set of identifiable vertices
• Critical random graphs and the structure of a minimum spanning tree
• Critical percolation on random regular graphs
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• A Unified View of Graph Searching
• The Evolution of Random Graphs
• Component behavior near the critical point of the random graph process
• The number of connected sparsely edged graphs
• The distribution of the maximum Brownian excursion
• The Structure of a Random Graph at the Point of the Phase Transition
• The Distribution of Heights of Binary Trees and Other Simple Trees
• Diameters in Supercritical Random Graphs Via First Passage Percolation
• The Diameter of Sparse Random Graphs
• A combinatorial theorem for stochastic processes
• A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution
• On the height of trees
• The total progeny in a branching process and a related random walk
• Depth-First Search and Linear Graph Algorithms
• On the fluctuations of sums of random variables
• The diameter of sparse random graphs