{
  "id": "1101.0693",
  "version": "v2",
  "published": "2011-01-04T10:26:20.000Z",
  "updated": "2012-04-17T10:21:37.000Z",
  "title": "The C_\\ell-free process",
  "authors": [
    "Lutz Warnke"
  ],
  "comment": "34 pages, 5 figures. Minor revisions and additions",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The C_\\ell-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of C_\\ell is created. For every $\\ell \\geq 4$ we show that, with high probability as $n \\to \\infty$, the maximum degree is $O((n \\log n)^{1/(\\ell-1)})$, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the C_\\ell-free process typically terminates with $\\Theta(n^{\\ell/(\\ell-1)}(\\log n)^{1/(\\ell-1)})$ edges, which answers a question of Erd\\H{o}s, Suen and Winkler. This is the first result that determines the final number of edges of the more general H-free process for a non-trivial \\emph{class} of graphs H. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to `transfer' certain decreasing properties from the binomial random graph to the H-free process.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-04-17T10:21:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "binomial random graph",
      "differential equation method",
      "general h-free process",
      "adds edges chosen",
      "empty graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1101.0693W"
    }
  }
}