Bounded-size rules: the barely subcritical regime

DOI10.1017/S0963548314000261zbMATH Open1336.05113arXiv1212.5480OpenAlexW2158528727MaRDI QIDQ5495673FDOQ5495673

Authors: Shankar Bhamidi, Amarjit Budhiraja, Xuan Wang 

Publication date: 6 August 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Bounded-size rules are dynamic random graph processes which incorporate limited choice along with randomness in the evolution of the system. One starts with the empty graph and at each stage two edges are chosen uniformly at random. One of the two edges is then placed into the system according to a decision rule based on the sizes of the components containing the four vertices. For bounded-size rules, all components of size greater than some fixed $Kgeq1$ are accorded the same treatment. Writing $BS(t)$ for the state of the system with nt/2 edges, Spencer and Wormald proved that for such rules, there exists a critical time t_c such that when t< t_c the size of the largest component is of order $logn$ while for $t>t_c$, the size of the largest component is of order $n$. In this work we obtain upper bounds (that hold with high probability) of order $n^{2gamma}lo{g}^{4}n$, on the size of the largest component, at time instants $t_n=t_c-n^{-gamma}$, where $gammain(0,1/4)$. This result for the barely subcritical regime forms a key ingredient in the study undertaken in cite{amc-2012}, of the asymptotic dynamic behavior of the process describing the vector of component sizes and associated complexity of the components for such random graph models in the critical scaling window. The proof uses a coupling of BSR processes with a certain family of inhomogeneous random graphs with vertices in the type space $Rbol{d}_{+}imescD([0,infty):NN{N}_0)$ where $cD([0,infty):NN{N}_0)$ is the Skorohod $D$-space of functions that are right continuous and have left limits equipped with the usual Skorohod topology. The coupling construction also gives an alternative characterization (than the usual explosion time of the susceptibility function) of the critical time $t_c$ for the emergence of the giant component in terms of the operator norm of integral operators on certain $L^2$ spaces.

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

Recommendations

• The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
• Component behavior near the critical point of the random graph process
• The evolution of subcritical Achlioptas processes
• Birth control for giants
• The Bohman-Frieze process near criticality

zbMATH Keywords

decision ruledynamic random graph processes

Mathematics Subject Classification ID

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

Cites Work

• The phase transition in inhomogeneous random graphs
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Markov Chains
• The largest component in a subcritical random graph with a power law degree distribution
• Explosive percolation in random networks
• Mixing time of near-critical random graphs
• Avoiding a giant component
• Achlioptas process phase transitions are continuous
• Phase transitions for modified Erdős--Rényi processes
• Birth control for giants
• On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase
• The Bohman-Frieze process near criticality
• Susceptibility in subcritical random graphs

Cited In (5)

• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Convergence of Achlioptas processes via differential equations with unique solutions
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• On the largest component in the subcritical regime of the Bohman-Frieze process
• The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs

This page was built for publication: Bounded-size rules: the barely subcritical regime

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