On the largest component in the subcritical regime of the Bohman-Frieze process

Abstract

Kang, Perkins and Spencer showed that the size of the largest component of the Bohman-Frieze process at a fixed time $t$ smaller than $t_c$, the critical time for the process is $L_1(t)=\Omega (\log n/(t_c-t{)}^2)$ with high probability. They also conjectured that this is the correct order, that is $L_1(t)=O(\log n/(t_c-t{)}^2)$ with high probability for fixed $t$ smaller than $t_c$. Using a different approach, Bhamidi, Budhiraja and Wang showed that $L_1(t_n)=O((\log n{)}^4/(t_c-t_n{)}^2)$ with high probability for $t_n\le t_c-n^{-\gamma }$ where $\gamma \in (0,1/4)$. In this paper, we improve their result by showing that for any fixed $\lambda >0$, $L_1(t_n)=O(\log n/(t_c-t_n{)}^2)$ with high probability for $t_n\le t_c-\lambda n^{-1/3}$. In particular, this settles the conjecture of Kang, Perkins and Spencer. We also prove some generalizations for general bounded size rules.

References in corpus (4)

• Achlioptas process phase transitions are continuous
• The Bohman-Frieze Process Near Criticality
• Bounded-size rules: The barely subcritical regime
• The augmented multiplicative coalescent and critical dynamic random graph models

Cited by in corpus (1)

• Bounded-size rules: The barely subcritical regime