{
  "id": "1508.04675",
  "version": "v1",
  "published": "2015-08-19T15:11:27.000Z",
  "updated": "2015-08-19T15:11:27.000Z",
  "title": "Independent Sets, Matchings, and Occupancy Fractions",
  "authors": [
    "Ewan Davies",
    "Matthew Jenssen",
    "Will Perkins",
    "Barnaby Roberts"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of Kahn's result that a disjoint union of $K_{d,d}$'s maximizes the number of independent sets of a bipartite d-regular graph, Galvin and Tetali's result that the independence polynomial is maximized by the same, and Zhao's extension of both results to all d-regular graphs. For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a disjoint union of $K_{d,d}$'s. Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstrom. In probabilistic language, our main theorems state that for all d-regular graphs and all $\\lambda$, the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity $\\lambda$ are maximized by $K_{d,d}$. Our method involves constrained optimization problems over distributions of random variables and applies to all d-regular graphs directly, without a reduction to the bipartite case. Using a variant of the method we prove a lower bound on the occupancy fraction of the hard-core model on any d-regular, vertex-transitive, bipartite graph: the occupancy fraction of such a graph is strictly greater than the occupancy fraction of the unique translation-invariant hard-core measure on the infinite d-regular tree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-19T15:11:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "independent sets",
      "disjoint union",
      "hard-core model",
      "unique translation-invariant hard-core measure",
      "infinite d-regular tree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150804675D"
    }
  }
}