{
  "id": "1307.2041",
  "version": "v2",
  "published": "2013-07-08T11:23:38.000Z",
  "updated": "2013-08-21T07:23:29.000Z",
  "title": "On the largest component in the subcritical regime of the Bohman-Frieze process",
  "authors": [
    "Sanchayan Sen"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-08-21T07:23:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C80"
    ],
    "keywords": [
      "largest component",
      "bohman-frieze process",
      "high probability",
      "subcritical regime",
      "general bounded size rules"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1307.2041S"
    }
  }
}