{
  "id": "1203.6310",
  "version": "v2",
  "published": "2012-03-28T16:42:26.000Z",
  "updated": "2012-07-30T12:17:24.000Z",
  "title": "On Posa's conjecture for random graphs",
  "authors": [
    "Daniela Kühn",
    "Deryk Osthus"
  ],
  "comment": "includes minor revisions, accepted for publication in SIAM Journal Discrete Mathematics",
  "categories": [
    "math.CO"
  ],
  "abstract": "The famous Posa conjecture states that every graph of minimum degree at least 2n/3 contains the square of a Hamilton cycle. This has been proved for large n by Koml\\'os, Sark\\\"ozy and Szemer\\'edi. Here we prove that if p > n^{-1/2+\\eps}, then asymptotically almost surely, the binomial random graph G_{n,p} contains the square of a Hamilton cycle. This provides an `approximate threshold' for the property in the sense that the result fails to hold if p< n^{-1/2}.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-07-30T12:17:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C45"
    ],
    "keywords": [
      "posas conjecture",
      "hamilton cycle",
      "famous posa conjecture states",
      "binomial random graph",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.6310K"
    }
  }
}