Aggregation Models with Limited Choice and the Multiplicative Coalescent

作者：Bhamidi Shankar^*; Budhiraja Amarjit; Wang Xuan

来源：Random Structures and Algorithms, 2015, 46(1): 55-116.

DOI：10.1002/rsa.20493

• critical random graphs
• Bohman-Frieze model
• multiplicative coalescent
• entrance boundary
• giant component
• branching processes
• inhomogeneous random graphs

The percolation phase transition and the mechanism of the emergence of the giant component through the critical scaling window for random graph models, has been a topic of great interest in many different communities ranging from statistical physics, combinatorics, computer science, social networks and probability theory. The last few years have witnessed an explosion of models which couple random aggregation rules, that specify how one adds edges to existing configurations, and choice, wherein one selects from a limited set of edges at random to use in the configuration. While an intense study of such models has ensued, understanding the actual emergence of the giant component and merging dynamics in the critical scaling window has remained impenetrable to a rigorous analysis. In this work we take an important step in the analysis of such models by studying one of the standard examples of such processes, namely the Bohman-Frieze model, and provide first results on the asymptotic dynamics, through the critical scaling window, that lead to the emergence of the giant component for such models. We identify the scaling window and show that through this window, the component sizes properly rescaled converge to the standard multiplicative coalescent. Proofs hinge on a careful analysis of certain infinite-type branching processes with types taking values in the space of cadlag paths, and stochastic analytic techniques to estimate susceptibility functions of the components all the way through the scaling window where these functions explode. Previous approaches for analyzing random graphs at criticality have relied largely on classical breadth-first search techniques that exploit asymptotic connections with Brownian excursions. For dynamic random graph models evolving via general Markovian rules, such approaches fail and we develop a quite different set of tools that can potentially be used for the study of critical dynamics for all bounded size rules.

• 出版日期2015-1