{
  "id": "1008.4044",
  "version": "v1",
  "published": "2010-08-24T13:47:03.000Z",
  "updated": "2010-08-24T13:47:03.000Z",
  "title": "The K_4-free process",
  "authors": [
    "Guy Wolfovitz"
  ],
  "comment": "36 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the K_4-free process. In this process, the edges of the complete n-vertex graph are traversed in a uniformly random order, and each traversed edge is added to an initially empty evolving graph, unless the addition of the edge creates a copy of K_4. Let M(n) denote the graph that is produced by that process. We prove that a.a.s., the number of edges in M(n) is O( n^{8/5} (\\ln n)^{1/5} ). This matches, up to a constant factor, a lower bound of Bohman. As a by-product, we prove the following Ramsey-type result: for every n there exists a K_4-free n-vertex graph, in which the largest set of vertices that doesn't span a triangle has size O( n^{3/5} (\\ln n)^{1/5} ). This improves, by a factor of (\\ln n)^{3/10}, an upper bound of Krivelevich.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-08-24T13:47:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete n-vertex graph",
      "uniformly random order",
      "upper bound",
      "edge creates",
      "constant factor"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1008.4044W"
    }
  }
}