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
2083618772 2963702702 2033718639 2144865572
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. 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 copies of Kd;d maximizes the number of independent sets of a bipartite d-regular graph, Galvin and Tet ali'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 union of copies of Kd;d. 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 �, 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. 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 translationinvariant hard-core measure on the infinite d-regular tree We study matchings on sparse random graphs by means of the cavity method. We first show how the method reproduces several known results about maximum and perfect matchings in regular and Erd?s?R?nyi random graphs. Our main new result is the computation of the entropy, i.e.?the leading order of the logarithm of the number of solutions, of matchings with a given size. We derive both an algorithm to compute this entropy for an arbitrary graph with a girth that diverges in the large size limit, and an analytic result for the entropy in regular and Erd?s?R?nyi random graph ensembles. We give a sharp lower bound on the number of matchings of a given size in a bipartite graph. When specialized to regular bipartite graphs, our results imply Friedland's Lower Matching Conjecture and Schrijver's theorem proven by Gurvits and Csikvari. Indeed, our work extends the recent work of Csikvari done for regular and bi-regular bipartite graphs. Moreover, our lower bounds are order optimal as they are attained for a sequence of @math -lifts of the original graph as well as for random @math -lifts of the original graph when @math tends to infinity. We then extend our results to permanents and subpermanents sums. For permanents, we are able to recover the lower bound of Schrijver recently proved by Gurvits using stable polynomials. Our proof is algorithmic and borrows ideas from the theory of local weak convergence of graphs, statistical physics and covers of graphs. We provide new lower bounds for subpermanents sums and obtain new results on the number of matching in random @math -lifts with some implications for the matching measure and the spectral measure of random @math -lifts as well as for the spectral measure of infinite trees.