Independent Sets, Matchings, and Occupancy Fractions

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 $K_{d,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 $K_{d,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 $\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.

Typo corrected last equation pg 1

References in corpus (2)

• On replica symmetry of large deviations in random graphs
• Three tutorial lectures on entropy and counting

Cited by in corpus (5)

• On the hard sphere model and sphere packings in high dimensions
• Colouring triangle-free graphs with local list sizes
• Extremes of the internal energy of the Potts model on cubic graphs
• The number of independent sets in an irregular graph
• Tight bounds on the coefficients of partition functions via stability