{
  "id": "1206.1016",
  "version": "v1",
  "published": "2012-06-05T18:27:31.000Z",
  "updated": "2012-06-05T18:27:31.000Z",
  "title": "Mantel's Theorem for random graphs",
  "authors": [
    "Bobby DeMarco",
    "Jeff Kahn"
  ],
  "comment": "15 pages",
  "categories": [
    "math.PR",
    "cs.DM",
    "math.CO"
  ],
  "abstract": "For a graph $G$, denote by $t(G)$ (resp. $b(G)$) the maximum size of a triangle-free (resp. bipartite) subgraph of $G$. Of course $t(G) \\geq b(G)$ for any $G$, and a classic result of Mantel from 1907 (the first case of Tur\\'an's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e. for what $p=p(n)$) is the \"Erd\\H{o}s-R\\'enyi\" random graph $G=G(n,p)$ likely to satisfy $t(G) = b(G)$? We show that this is true if $p>C n^{-1/2} \\log^{1/2}n $ for a suitable constant $C$, which is best possible up to the value of $C$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-05T18:27:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D40",
      "05C35",
      "05C80"
    ],
    "keywords": [
      "random graph",
      "mantels theorem",
      "natural question",
      "complete graphs",
      "equality holds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.1016D"
    }
  }
}