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 Tet ali, and Zhao showing that a union of copies of @math 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 @math . Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstr "om. In probabilistic language, our main theorems state that for all d-regular graphs and all @math , the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity @math are maximized by @math . 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.
For matchings, Carroll, Galvin, and Tet ali @cite_12 used the entropy method to give an upper bound of @math on @math over @math -regular graphs. It was previously conjectured (eg. @cite_16 @cite_15 ) that @math maximizes @math over all @math -regular graphs. This is an implication of our Theorem .
@cite_15 @cite_16 @cite_12
1593988169 2155237361 2083618772
We explain the notion of the entropy of a discrete random variable, and derive some of its basic properties. We then show through examples how entropy can be useful as a combinatorial enumeration tool. We end with a few open questions. For the set of graphs with a given degree sequence, consisting of any number of @math and @math , and its subset of bipartite graphs, we characterize the optimal graphs who maximize and minimize the number of @math -matchings. We find the expected value of the number of @math -matchings of @math -regular bipartite graphs on @math vertices with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for @math -matchings in @math -regular bipartite graphs on @math vertices, and their asymptotic versions for infinite @math -regular bipartite graphs. We prove these conjectures for @math -regular bipartite graphs and for @math -matchings with @math . We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size @? in a d-regular graph on N vertices. For [email protected]?N bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size @? in the graph consisting of N2d disjoint copies of K"d","d. This provides asymptotic evidence for a conjecture of S. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.