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.
Recall that @math is called the partition function. A crucial observation made by Csikv 'ari @cite_48 is that for any @math -lift @math of a bipartite graph @math , we have @math , see Proposition in the sequel. Note that a @math -lift of a @math -regular graph is still @math -regular. Starting form any @math -regular bipartite graph @math , Csikv 'ari builds a sequence of @math -lifts with increasing girth. Then Csikv 'ari uses the framework of local weak convergence in order to define a limiting graph for the sequence of @math -lifts. In this particular case, the limit is the infinite @math -regular tree. Using the connection between the local weak convergence and the matching measure of a graph developed in @cite_31 , Csikv 'ari computes a limiting partition function associated to this infinite @math -regular tree which is obtained from the Kesten-McKay measure. This limiting partition function is then a lower bound for the original partition function @math and the lower bounds ) and ) are then easily obtained by properly choosing the parameter @math as a function of @math the size of the matchings that we need to count.
@cite_48 @cite_31
2144865572 2963702702 2128943288 2011571064
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. 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 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. We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [16]. Let Z ∞ d be the infinite graph whose vertex set is Zd and which has an edge (u,v) whenever ||u-v|| ∞ = 1. Let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of Z ∞d . The growth rate of G, denoted ρ G , is the minimum ρ such that every ball of radius r > 1 in G contains at most rρ vertices. By simple volume arguments, dim(G) = Ω(ρ G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ G ) for every graph G.Previously, it was not known whether dim(G) could be upper bounded by any function of ρ G , even in the special case of trees. We show that a weaker form of Levin's conjecture holds by proving that, for every graph G, dim(G) = O(ρ G log ρ G ). We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) =Ω(ρ G log ρ G ). For families of graphs which exclude a fixed minor, we salvage the strong form, showing that dim(G) = O(ρ G ). This holds also for graphs without long induced simple cycles. Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces due to Linial[15].