The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs

DOI10.1007/S00440-013-0540-XMaRDI QIDQ483318zbMATH OpenOpenAlexFDO

Authors Shankar Bhamidi, Amarjit Budhiraja, Xuan Wang

Publication date 16 December 2014

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.5493

zbMATH Keywords

branching processescritical random graphsentrance boundarydifferential equation methodAchlioptas processbounded-size rulesgiant componentmultiplicative coalescentinhomogeneous random graphssurplusdynamic random graph modelsscaling window

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Abstract: Random graph models with limited choice have been studied extensively with the goal of understanding the mechanism of the emergence of the giant component. One of the standard models are the Achlioptas random graph processes on a fixed set of $n$ vertices. Here at each step, one chooses two edges uniformly at random and then decides which one to add to the existing configuration according to some criterion. An important class of such rules are the bounded-size rules where for a fixed $Kgeq1$, all components of size greater than $K$ are treated equally. While a great deal of work has gone into analyzing the subcritical and supercritical regimes, the nature of the critical scaling window, the size and complexity (deviation from trees) of the components in the critical regime and nature of the merging dynamics has not been well understood. In this work we study such questions for general bounded-size rules. Our first main contribution is the construction of an extension of Aldous's standard multiplicative coalescent process which describes the asymptotic evolution of the vector of sizes and surplus of all components. We show that this process, referred to as the standard augmented multiplicative coalescent (AMC) is `nearly' Feller with a suitable topology on the state space. Our second main result proves the convergence of suitably scaled component size and surplus vector, for any bounded-size rule, to the standard AMC. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from [8], on the size of the largest component in the barely subcritical regime.

Recommendations

• Bounded-size rules: the barely subcritical regime
• The evolution of subcritical Achlioptas processes
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Component behavior near the critical point of the random graph process
• Connectivity thresholds for bounded size rules

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3173143 (Why is no real title available?)
• scientific article; zbMATH DE number 44889 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Achlioptas process phase transitions are continuous
• Aggregation models with limited choice and the multiplicative coalescent
• Avoiding a giant component
• Birth control for giants
• Bounded-size rules: the barely subcritical regime
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Critical random graphs and the structure of a minimum spanning tree
• Explosive percolation in random networks
• Novel scaling limits for critical inhomogeneous random graphs
• On a random graph with immigrating vertices: Emergence of the giant component
• On the Infinitesimal Generators of Integral Convolutions
• Phase transitions for modified Erdős--Rényi processes
• Probability. Theory and examples.
• Random graphs.
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• The Bohman-Frieze process near criticality
• The continuum limit of critical random graphs
• The continuum random tree. I
• The evolution of subcritical Achlioptas processes
• The phase transition in inhomogeneous random graphs

Cited in

(21)

• A probabilistic approach to the leader problem in random graphs
• Scaling limits of random trees and random graphs
• Aggregation models with limited choice and the multiplicative coalescent
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Parking on Cayley trees and frozen Erdős-Rényi
• Big jobs arrive early: from critical queues to random graphs
• Convergence of Achlioptas processes via differential equations with unique solutions
• On moments of multiplicative coalescents
• Stable graphs: distributions and line-breaking construction
• Connectivity thresholds for bounded size rules
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Continuum limit of critical inhomogeneous random graphs
• Critical random forests
• Sesqui-type branching processes
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• Heavy-tailed configuration models at criticality
• Bounded-size rules: the barely subcritical regime
• Critical random graphs and the differential equations technique
• A new encoding of coalescent processes: applications to the additive and multiplicative cases
• The eternal multiplicative coalescent encoding via excursions of Lévy-type processes
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees

This page was built for publication: The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs

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