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

S. Sen

Research output: Contribution to journalArticleAcademicpeer-review

14 Downloads (Pure)

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\leq 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\leq 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.
Original languageEnglish
Article number64
Number of pages15
JournalElectronic Communications in Probability
Volume21
DOIs
Publication statusPublished - 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'On the largest component in the subcritical regime of the Bohman-Frieze process'. Together they form a unique fingerprint.

Cite this