{
  "id": "0912.4861",
  "version": "v1",
  "published": "2009-12-24T13:47:15.000Z",
  "updated": "2009-12-24T13:47:15.000Z",
  "title": "Conjecture on the maximum cut and bisection width in random regular graphs",
  "authors": [
    "Lenka Zdeborová",
    "Stefan Boettcher"
  ],
  "comment": "12 pages",
  "journal": "J. Stat. Mech. (2010) P02020",
  "doi": "10.1088/1742-5468/2010/02/P02020",
  "categories": [
    "cond-mat.dis-nn",
    "cs.DM",
    "math.CO"
  ],
  "abstract": "Asymptotic properties of random regular graphs are object of extensive study in mathematics. In this note we argue, based on theory of spin glasses, that in random regular graphs the maximum cut size asymptotically equals the number of edges in the graph minus the minimum bisection size. Maximum cut and minimal bisection are two famous NP-complete problems with no known general relation between them, hence our conjecture is a surprising property of random regular graphs. We further support the conjecture with numerical simulations. A rigorous proof of this relation is obviously a challenge.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-12-24T13:47:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random regular graphs",
      "bisection width",
      "conjecture",
      "maximum cut size asymptotically equals",
      "minimal bisection"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "journal": "Journal of Statistical Mechanics: Theory and Experiment",
      "year": 2010,
      "month": "Feb",
      "volume": 2010,
      "number": 2,
      "pages": 2020
    },
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010JSMTE..02..020Z"
    }
  }
}