The continuum limit of critical random graphs

DOI10.1007/S00440-010-0325-4zbMath1239.05165OpenAlexW2104099158MaRDI 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 walksrandom graphsdiameterGromov-Hausdorff distancebijectionscaling limitscontinuum random treedistances in critical random graphs

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Distance in graphs (05C12) Random walks on graphs (05C81)

Related Items (50)

Exceptional times of the critical dynamical Erdős-Rényi graph ⋮ The critical window in random digraphs ⋮ Unusually large components in near-critical Erdős–Rényi graphs via ballot theorems ⋮ The scaling limits of the minimal spanning tree and invasion percolation in the plane ⋮ Tail bounds for the height and width of a random tree with a given degree sequence ⋮ Depth first exploration of a configuration model ⋮ Scaling limits of stochastic processes associated with resistance forms ⋮ A new encoding of coalescent processes: applications to the additive and multiplicative cases ⋮ The hyperbolic Brownian plane ⋮ Critical percolation on scale-free random graphs: new universality class for the configuration model ⋮ Universality for critical heavy-tailed network models: metric structure of maximal components ⋮ A probabilistic approach to the leader problem in random graphs ⋮ On breadth‐first constructions of scaling limits of random graphs and random unicellular maps ⋮ Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023 ⋮ Convergence of blanket times for sequences of random walks on critical random graphs ⋮ The scaling limit of a critical random directed graph ⋮ The probability of unusually large components for critical percolation on random \(d\)-regular graphs ⋮ Exact enumeration of satisfiable 2-SAT formulae ⋮ Stable graphs: distributions and line-breaking construction ⋮ Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs ⋮ Scaling Limits of Markov-Branching Trees and Applications ⋮ Multisource invasion percolation on the complete graph ⋮ Models of random subtrees of a graph ⋮ Distances in \(\frac{1}{\|x-y\|^{2d}}\) percolation models for all dimensions ⋮ Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes ⋮ Scaling limit for the random walk on the largest connected component of the critical random graph ⋮ Noise sensitivity of critical random graphs ⋮ Feller property of the multiplicative coalescent with linear deletion ⋮ Unnamed Item ⋮ Scaling Limits of Random Trees and Random Graphs ⋮ Big Jobs Arrive Early: From Critical Queues to Random Graphs ⋮ Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ 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 ⋮ Critical random graphs and the differential equations technique ⋮ The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs ⋮ Continuum limit of critical inhomogeneous random graphs ⋮ Asymptotics of trees with a prescribed degree sequence and applications ⋮ The size of the giant component in random hypergraphs: a short proof ⋮ Critical random forests ⋮ Geometry of the minimal spanning tree of a random 3-regular graph ⋮ The probability of unusually large components in the near-critical Erdős–Rényi graph ⋮ Speeding up non-Markovian first-passage percolation with a few extra edges ⋮ Limits of multiplicative inhomogeneous random graphs and Lévy trees: limit theorems ⋮ The eternal multiplicative coalescent encoding via excursions of Lévy-type processes ⋮ Global lower mass-bound for critical configuration models in the heavy-tailed regime ⋮ Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs ⋮ The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees ⋮ Anomalous Behavior of Random Walks on Disordered Media

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
• 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
• Enumerating graphs and Brownian motion
• On a random graph with immigrating vertices: Emergence of the giant component
• 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

This page was built for publication: The continuum limit of critical random graphs