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

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI Euclid arXiv