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

DOI10.1007/S00440-013-0540-XzbMATH Open1318.60012arXiv1212.5493OpenAlexW2028633127MaRDI QIDQ483318FDOQ483318

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)

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.

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

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

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)

Cites Work

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

Cited In (21)

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

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)