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

S. Sen

Research output: Contribution to journalArticleAcademicpeer-review

14 Downloads (Pure)

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)=\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.
Original languageEnglish
Number of pages22
JournalarXiv
DOIs
Publication statusPublished - 2014
Externally publishedYes

Fingerprint

Generalization

Cite this

@article{a8e274de59434ff9a7702b297b664a1a,
title = "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)=\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.",
author = "S. Sen",
year = "2014",
doi = "10.1214/16-ecp20",
language = "English",
journal = "arXiv",
publisher = "Cornell University Library",

}

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

In: arXiv, 2014.

Research output: Contribution to journalArticleAcademicpeer-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 -