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.
As explained in the sequel of this section, all the basic ideas used in our proofs were present in a form or another in the literature: using lifts for extremal graph theory was one the main motivation for their introduction in a series of papers by Amit, Linial, Matousek, Rozenman and Bilu @cite_45 @cite_5 @cite_14 @cite_35 ; the matching measure and the local recursions already appeared in the seminal work of Heilmann and Lieb @cite_13 ; the function @math defined in ) is known in statistical physics as the Bethe entropy @cite_36 . The main contribution of this paper is a conceptual message showing how known techniques from interdisciplinary areas can lead to new applications in theoretical computer science. In the next subsections, we will try to relate our results to the existing literature and give credit to the many authors who inspired our work.
@cite_35 @cite_14 @cite_36 @cite_45 @cite_5 @cite_13
2962992640 1971907125 2033718639 1974893148 1998836349 2037389370
Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map � : H → G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2lift such that all new eigenvalues are in the range [−2 √ d − 1,2 √ d − 1] (If true, this is tight , e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all For a graph G, a random n-lift of G has the vertex set V(G) × [n] and for each edge [u, v] ∈ E(G), there is a random matching between u × [n] and v × [n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n → ∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χf, we show that the chromatic number of typical lifts is bounded from below by const. √χ log χ and also by const. χf log2 χf (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ log χ). Many interesting problems remain open. 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. In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n ,w e form a random graphby replacing eachvertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G .T h e resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also “randomizing” given graphs. The main specific result that we prove here (Theorem 1) is that if δ ≥ 3 is the smallest vertex degree in G, then almost all n-covers of G are δconnected. In subsequent papers we will address oth er graphproperties, suchas girth , expansion and chromatic number. We study random lifts of a graph G as defined in [1]. We prove a 0-1 law which states that for every graph G either almost every lift of G has a perfect matching, or almost none of its lifts has a perfect matching. We provide a precise description of this dichotomy. Roughly speaking, the a.s. existence of a perfect matching in the lift depends on the existence of a fractional perfect matching in G. The precise statement appears in Theorem 1. 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.