{
  "id": "1507.02089",
  "version": "v1",
  "published": "2015-07-08T10:20:35.000Z",
  "updated": "2015-07-08T10:20:35.000Z",
  "title": "Zero-free regions of partition functions with applications to algorithms and graph limits",
  "authors": [
    "Guus Regts"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "Based on a technique of Barvinok and Barvinok and Sober\\'on we identify a class of edge-coloring models whose partition functions do not evaluate to zero on bounded degree graphs. Subsequently we give a quasi-polynomial time approximation scheme for computing these partition functions. As another application we show that the normalised partition functions of these models are continuous with respect the Benjamini-Schramm topology on bounded degree graphs. We moreover give quasi-polynomial time approximation schemes for evaluating a large class of graph polynomials, including the Tutte polynomial, on bounded degree graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-07-08T10:20:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C85",
      "05C31",
      "68W25",
      "05C99"
    ],
    "keywords": [
      "partition functions",
      "graph limits",
      "bounded degree graphs",
      "quasi-polynomial time approximation scheme",
      "zero-free regions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150702089R"
    }
  }
}