# zbMATH — the first resource for mathematics

On the largest component in the subcritical regime of the Bohman-Frieze process. (English) Zbl 1346.60006
Summary: M. Kang et al. [Random Struct. Algorithms 43, No. 2, 221–250 (2013; Zbl 1272.05180); erratum ibid. 46, No. 4, 801 (2015; Zbl 1330.05145)] conjectured 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)=O(\log n/(t_c-t)^2)$$ with high probability. S. Bhamidi et al. [Random Struct. Algorithms 46, No. 1, 55–116 (2015; Zbl 1307.05200)] have shown that a bound of the form $$L_1(t_n)=O((\log n)^4/(t_c-t_n)^2)$$ holds with high probability for $$t_n\leq t_c-n^{-\gamma }$$ where $$\gamma \in (0,1/4)$$. In this paper, we improve the result in [loc. cit.] 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 in [Kang et al., loc .cit.].

##### MSC:
 60C05 Combinatorial probability 05C80 Random graphs (graph-theoretic aspects)
Full Text: