### Abstract

Original language | English |
---|---|

Number of pages | 22 |

Journal | arXiv |

DOIs | |

Publication status | Published - 2014 |

Externally published | Yes |

### Fingerprint

### Cite this

}

**On the largest component in the subcritical regime of the Bohman-Frieze process.** / Sen, S.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

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

AU - Sen, S.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://arxiv.org/pdf/1307.2041v2.pdf

U2 - 10.1214/16-ecp20

DO - 10.1214/16-ecp20

M3 - Article

JO - arXiv

JF - arXiv

ER -