Projects per year
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.
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 language | English |
---|---|
Pages (from-to) | 47–66 |
Number of pages | 20 |
Journal | Journal of the London Mathematical Society |
Volume | 96 |
Issue number | 1 |
Early online date | 26 Jun 2017 |
DOIs | |
Publication status | Published - Aug 2017 |
Fingerprint
Dive into the research topics of 'Independent sets, matchings, and occupancy fractions'. Together they form a unique fingerprint.Projects
- 1 Finished
-
New approaches to Gibbs measures at the interface of probability and computational complexity
Perkins, W. (Principal Investigator)
Engineering & Physical Science Research Council
1/01/17 → 31/12/18
Project: Research Councils