{
  "id": "0908.3778",
  "version": "v1",
  "published": "2009-08-26T09:31:36.000Z",
  "updated": "2009-08-26T09:31:36.000Z",
  "title": "Extremal Subgraphs of Random Graphs: an Extended Version",
  "authors": [
    "Graham Brightwell",
    "Konstantinos Panagiotou",
    "Angelika Steger"
  ],
  "comment": "36 pages, 2 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We prove that there is a constant $c >0$, such that whenever $p \\ge n^{-c}$, with probability tending to 1 when $n$ goes to infinity, every maximum triangle-free subgraph of the random graph $G_{n,p}$ is bipartite. This answers a question of Babai, Simonovits and Spencer (Journal of Graph Theory, 1990). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with $M$ edges, where $M >> n$, is ``nearly unique''. More precisely, given a maximum cut $C$ of $G_{n,M}$, we can obtain all maximum cuts by moving at most $O(\\sqrt{n^3/M})$ vertices between the parts of $C$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-08-26T09:31:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C35",
      "60C05"
    ],
    "keywords": [
      "random graph",
      "extremal subgraphs",
      "extended version",
      "maximum cut",
      "maximum triangle-free subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0908.3778B"
    }
  }
}