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, Unnamed Item, Anomalous Behavior of Random Walks on Disordered Media, Big Jobs Arrive Early: From Critical Queues to Random Graphs, 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, Asymptotics of trees with a prescribed degree sequence and applications, The critical window in random digraphs, Unusually large components in near-critical Erdős–Rényi graphs via ballot theorems, 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, 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, Exceptional times of the critical dynamical Erdős-Rényi graph, The scaling limits of the minimal spanning tree and invasion percolation in the plane, Scaling limits of stochastic processes associated with resistance forms, The hyperbolic Brownian plane, Feller property of the multiplicative coalescent with linear deletion, Network models: structure and function. Abstracts from the workshop held December 10--16, 2017, Critical random graphs and the differential equations technique, The size of the giant component in random hypergraphs: a short proof, Geometry of the minimal spanning tree of a random 3-regular graph, Limits of multiplicative inhomogeneous random graphs and Lévy trees: limit theorems, 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, Depth first exploration of a configuration model, Universality for critical heavy-tailed network models: metric structure of maximal components, Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs, The eternal multiplicative coalescent encoding via excursions of Lévy-type processes, Critical percolation on scale-free random graphs: new universality class for the configuration model, Noise sensitivity of critical random graphs, Tail bounds for the height and width of a random tree with a given degree sequence, Scaling Limits of Random Trees and Random Graphs

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