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.
In @cite_31 , Csikv 'a ri proved the lower matching conjecture' of @cite_16 and in @cite_22 gave a new lower bound on the number of perfect matchings of @math -regular, vertex-transitive, bipartite graphs, in both comparing an arbitrary graph with the infinite @math -regular tree (see also the recent extension by Lelarge @cite_13 to irregular graphs). Proposition 2.10 in @cite_22 states that the edge occupancy fraction of any @math -regular, vertex-transitive, bipartite graph is at least that of the infinite @math -regular tree; in Theorem we prove an analogous result for independent sets. Csikv 'a ri's techniques in the two papers are different than the methods of this paper, but similar in that he bounds the occupancy fraction instead of directly working with the partition function. His results rely on an elegant interplay between the Heilman-Lieb theorem @cite_4 and Benjamini-Schramm convergence of bounded-degree graphs.
@cite_4 @cite_22 @cite_31 @cite_16 @cite_13
2037389370 1485502831 2128943288 2155237361 2144865572
We investigate the general monomer-dimer partition function,P(x), which is a polynomial in the monomer activity,x, with coefficients depending on the dimer activities. Our main result is thatP(x) has its zeros on the imaginary axis when the dimer activities are nonnegative. Therefore, no monomer-dimer system can have a phase transition as a function of monomer density except, possibly, when the monomer density is minimal (i.e.x=0). Elaborating on this theme we prove the existence and analyticity of correlation functions (away fromx=0) in the thermodynamic limit. Among other things we obtain bounds on the compressibility and derive a new variable in which to make an expansion of the free energy that converges down to the minimal monomer density. We also relate the monomer-dimer problem to the Heisenberg and Ising models of a magnet and derive Christoffell-Darboux formulas for the monomer-dimer and Ising model partition functions. This casts the Ising model in a new light and provides an alternative proof of the Lee-Yang circle theorem. We also derive joint complex analyticity domains in the monomer and dimer activities. Our considerations are independent of geometry and hence are valid for any dimensionality. A theorem of A. Schrijver asserts that a d-regular bipartite graph on 2n vertices has at least @math perfect matchings. L. Gurvits gave an extension of Schrijver’s theorem for matchings of density p. In this paper we give a stronger version of Gurvits’s theorem in the case of vertex-transitive bipartite graphs. This stronger version in particular implies that for every positive integer k, there exists a positive constant c(k) such that if a d-regular vertex-transitive bipartite graph on 2n vertices contains a cycle of length at most k, then it has at least @math perfect matchings. Friedland's Lower Matching Conjecture asserts that if @math is a @math --regular bipartite graph on @math vertices, and @math denotes the number of matchings of size @math , then @math where @math . When @math , this conjecture reduces to a theorem of Schrijver which says that a @math --regular bipartite graph on @math vertices has at least @math perfect matchings. L. Gurvits proved an asymptotic version of the Lower Matching Conjecture, namely he proved that @math In this paper, we prove the Lower Matching Conjecture. In fact, we will prove a slightly stronger statement which gives an extra @math factor compared to the conjecture if @math is separated away from @math and @math , and is tight up to a constant factor if @math is separated away from @math . We will also give a new proof of Gurvits's and Schrijver's theorems, and we extend these theorems to @math --biregular bipartite graphs. 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 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.