Journal
RANDOM STRUCTURES & ALGORITHMS
Volume 58, Issue 1, Pages 34-67Publisher
WILEY
DOI: 10.1002/rsa.20966
Keywords
critical random graphs; entrance boundary; Erdos-Renyi random graph; inhomogeneous random graphs; Markov processes; multiplicative coalescent
Funding
- NSERC [341845]
- NSF [DMS-1613072, DMS-1606839]
- ARO [W911NF-17-1-0010]
- CRM-ISM fellowship
- MATRICS grant from SERB [MTR/2019/000745]
- Infosys Foundation, Bangalore
Ask authors/readers for more resources
This study investigates the fixation time of the leader's identity in the general setting of Aldous's multiplicative coalescent, showing tightness in the Brownian regime and one-sided tightness in the heavy-tailed case. The findings demonstrate differences in the possible behavior in the two regimes, with explicit determination of median value of fixation time and generalization of results on Erdos-Renyi random graph.
We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the evolution of the component sizes of a wide array of near-critical coalescent processes, including the classical Erdos-Renyi process. We show tightness of the fixation time in the Brownian regime, explicitly determining the median value of the fixation time to within an optimalO(1) window. This generalizes Luczak's result for the Erdos-Renyi random graph using completely different techniques. In the heavy-tailed case, in which the limit of the component sizes can be encoded using a thinned pure-jump Levy process, we prove that only one-sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available