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

preprint2013arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.