Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs

DOI10.1214/20-AOP1472MaRDI QIDQ2227717zbMATH OpenOpenAlexFDO

Authors Raphaël Rossignol

Publication date 15 February 2021

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.09101, https://projecteuclid.org/euclid.aop/1611306382

zbMATH Keywords

coalescencedynamical percolationErdős-RényiFeller propertyfragmentationGromov-Hausdorff-Prokhorov distancerandom graphscaling limit

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Consider a critical Erd"os-R'enyi random graph: $n$ is the number of vertices, each one of the $$ possible edges is kept in the graph independently from the others with probability $n^{-1}+lambda{n}^{-4/3}$, $lambda$ being a fixed real number. When $n$ goes to infinity, Addario-Berry, Broutin and Goldschmidt have shown that the collection of connected components, viewed as suitably normalized measured compact metric spaces, converges in distribution to a continuous limit $mathcal{G}_{l}ambda$ made of random real graphs. In this paper, we consider notably the dynamical percolation on critical Erd"os-R'enyi random graphs. To each pair of vertices is attached a Poisson process of intensity $n^{-1/3}$, and every time it rings, one resamples the corresponding edge. Under this process, the collection of connected components undergoes coalescence and fragmentation. We prove that this process converges in distribution, as $n$ goes to infinity, towards a fragmentation-coalescence process on the continuous limit $mathcal{G}_{l}ambda$. We also prove convergence of discrete coalescence and fragmentation processes and provide Feller-type properties associated to fragmentation and coalescence.

Review text

Consider Erdős-Rényi random graphs \(\mathcal G(n,p)\) obtained from the complete graph with \(n \) vertices by deleting edges independently with probability \(1-p\). As \(n\to \infty\), there is a critical phase when \(p:=p(\lambda, n) =\frac 1 n + \frac \lambda {n^{4/3}}\) for some \(\lambda \in{\mathbb R}\). It was proved in [\textit{L. Addario-Berry} et al., Probab. Theory Relat. Fields 152, No. 3--4, 367--406 (2012; Zbl 1239.05165)] that the critical Erdős-Rényi random graphs with appropriate scalings convergence for the Gromov-Hausdorff topology to \(\mathcal G_\lambda\), a collection of real random graphs. In [\textit{L. Addario-Berry} et al., Ann. Probab. 45, No. 5, 3075--3144 (2017; Zbl 1407.60013)], the convergence was proved for the Gromov-Hausdorff-Prokhorov topology. In the present paper, a dynamical percolation on critical Erdős-Rényi random graphs \(\mathcal G(n,p)\) is considered. It can be constructed from two Poisson processes associated to each edges of the complete graph. One process determines the times when an edge is added (or kept if there is already one) and the second process determines the times when an edge is deleted (if there is one). A dynamical percolation process can also be constructed on the continuous limit \(\mathcal G_\lambda\). It is shown that under appropriate scalings, this process is the limit of the dynamical percolation process starting from a critical Erdős-Rényi random graph. The appropriate topology is a new intricate version of the Gromov-Hausdorff-Prokhorov distance. The proofs require a detailed analysis of the structure of a multigraph and rely on the properties of the multiplicative coalescent obtained in [\textit{D. Aldous}, Ann. Probab. 25, No. 2, 812--854 (1997; Zbl 0877.60010)]. Convergence is also established for the coalescence process and for the fragmentation process under appropriate scalings. In the first case, edges are never deleted and a Poisson process determines the times where edges are added whilst in the second case, edges are never added and a Poisson process determines the times where edges are deleted.

Recommendations

• Exceptional times of the critical dynamical Erdős-Rényi graph
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: limit theorems
• The continuum limit of critical random graphs
• Dynamic Erdős-Rényi graphs
• Achlioptas process phase transitions are continuous
• Triangle percolation in mean field random graphs-with PDE
• On a random graph evolving by degrees
• Scaling limit for the random walk on the largest connected component of the critical random graph
• Lack of hyperbolicity in asymptotic Erdős-Renyi sparse random graphs
• A dynamic Erdős-Rényi graph model

Cites work

• A course in metric geometry
• A new encoding of coalescent processes: applications to the additive and multiplicative cases
• A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Continuum limit of critical inhomogeneous random graphs
• Convergence of stochastic processes
• Critical random graphs: limiting constructions and distributional properties
• Critical window for the configuration model: finite third moment degrees
• Dynamical percolation
• Exceptional times of the critical dynamical Erdős-Rényi graph
• Heavy-tailed configuration models at criticality
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
• Optimal Transport
• Random measures, theory and applications
• Rayleigh processes, real trees, and root growth with re-grafting
• Tessellations of random maps of arbitrary genus
• The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
• The birth of the giant component
• The continuum limit of critical 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 limits of near-critical and dynamical percolation
• The standard additive coalescent
• Universality for critical heavy-tailed network models: metric structure of maximal components

Cited in

(14)

• Exceptional times of the critical dynamical Erdős-Rényi graph
• Hydrodynamic limit of the zero range process on a randomly oriented graph
• The continuum limit of critical random graphs
• Critical percolation on scale-free random graphs: new universality class for the configuration model
• Noise sensitivity of critical random graphs
• Scaling limit for the random walk on the largest connected component of the critical random graph
• Bounds for the annealed return probability on large finite percolation graphs
• Limit density of connected components in a graph process
• Unusually large components in near-critical Erdős–Rényi graphs via ballot theorems
• Noise sensitivity of percolation via differential inequalities
• The probability of unusually large components for critical percolation on random d-regular graphs
• Parking on Cayley trees and frozen Erdős-Rényi
• Noise sensitivity of the minimum spanning tree of the complete graph
• Fluid limit and gelation in the frozen Erdős-Rényi random graph

This page was built for publication: Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227717)