Independent sets, matchings, and occupancy fractions

Ewan Davies, Matthew Jenssen, Will Perkins, Barnaby Roberts

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)
210 Downloads (Pure)

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 the results of Kahn, Galvin and Tetali, and Zhao showing that a union of copies of Kd,d maximizes the number of independent sets and the independence polynomial of a d-regular graph.
For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a union of copies of Kd,d. Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markström.
In probabilistic language, our main theorems state that for all d-regular graphs and all λ, the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity λ are maximized by Kd,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.
Original languageEnglish
Pages (from-to)47–66
Number of pages20
JournalJournal of the London Mathematical Society
Volume96
Issue number1
Early online date26 Jun 2017
DOIs
Publication statusPublished - Aug 2017

Fingerprint

Dive into the research topics of 'Independent sets, matchings, and occupancy fractions'. Together they form a unique fingerprint.

Cite this