{
  "id": "cond-mat/0309348",
  "version": "v1",
  "published": "2003-09-15T12:53:54.000Z",
  "updated": "2003-09-15T12:53:54.000Z",
  "title": "Maximum matching on random graphs",
  "authors": [
    "Haijun Zhou",
    "Zhong-can Ou-Yang"
  ],
  "comment": "7 pages with 2 eps figures included. Use EPL style. Submitted to Europhysics Letters",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech"
  ],
  "abstract": "The maximum matching problem on random graphs is studied analytically by the cavity method of statistical physics. When the average vertex degree \\mth{c} is larger than \\mth{2.7183}, groups of max-matching patterns which differ greatly from each other {\\em gradually} emerge. An analytical expression for the max-matching size is also obtained, which agrees well with computer simulations. Discussion is made on this {\\em continuous} glassy phase transition and the absence of such a glassy phase in the related minimum vertex covering problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2003-09-15T12:53:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graphs",
      "maximum matching",
      "related minimum vertex covering problem",
      "glassy phase transition",
      "average vertex degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003cond.mat..9348Z"
    }
  }
}