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

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) = O m e g a (l o g n / (t_{c} - t)^{2})

with high probability. They also conjectured that this is the correct order, that is

L_{1} (t) = O (l o g 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 ((l o g n)^{4} / (t_{c} - t_{n})^{2})

with high probability for

t_{n} l e q t_{c} - n^{- g a m m a}

where

g a m m a i n (0, 1 / 4)

. In this paper, we improve their result by showing that for any fixed

l a m b d a > 0

,

L_{1} (t_{n}) = O (l o g n / (t_{c} - t_{n})^{2})

with high probability for

t_{n} l e q t_{c} - l a m b d a n^{- 1 / 3}

. In particular, this settles the conjecture of Kang, Perkins and Spencer. We also prove some generalizations for general bounded size rules.

Recommendations

Cited in

(1)

This page was built for publication: On the largest component in the subcritical regime of the Bohman-Frieze process