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 statistical physics, the analogue of the occupancy fraction in a general spin system is called the ; on general graphs it is @math -hard to compute the magnetization in the ferromagnetic Ising model, the monomer-dimer model, and the hard-core model @cite_21 @cite_3 .
@cite_21 @cite_3
2215999167 2570168223 2122772637 2037389370
We study the computational complexity of several natural problems arising in statistical physics and combinatorics. In particular, we consider the following problems: the mean magnetization and mean energy of the Ising model (both the ferromagnetic and the anti-ferromagnetic settings), the average size of an independent set in the hard core model, and the average size of a matching in the monomer-dimer model. We prove that for all non-trivial values of the underlying model parameters, exactly computing these averages is #P-hard. In contrast to previous results of Sinclair and Srivastava (2013) for the mean magnetization of the ferromagnetic Ising model, our approach does not use any Lee-Yang type theorems about the complex zeros of partition functions. Indeed, it was due to the lack of suitable Lee-Yang theorems for models such as the anti-ferromagnetic Ising model that some of the problems we study here were left open by Sinclair and Srivastava. In this paper, we instead use some relatively simple and well-known ideas from the theory of automatic symbolic integration to complete our hardness reductions. We study the complexity of computing average quantities related to spin systems, such as the mean magnetization and susceptibility in the ferromagnetic Ising model, and the average dimer count (or average size of a matching) in the monomer-dimer model. By establishing connections between the complexity of computing these averages and the location of the complex zeros of the partition function, we show that these averages are #P-hard to compute, and hence, under standard assumptions, computationally intractable. In the case of the Ising model, our approach requires us to prove an extension of the famous Lee–Yang Theorem from the 1950s. The subject of this article is spin-systems as studied in statistical physics. We focus on the case of two spins. This case encompasses models of physical interest, such as the classical Ising model (ferromagnetic or antiferromagnetic, with or without an applied magnetic field) and the hard-core gas model. There are three degrees of freedom, corresponding to our parameters beta, gamma and mu. We wish to study the complexity of (approximately) computing the partition function in terms of these parameters. We pay special attention to the symmetric case mu=1 for which our results are depicted in Figure 1. Exact computation of the partition function Z is NP-hard except in the trivial case beta gamma=1, so we concentrate on the issue of whether Z can be computed within small relative error in polynomial time. We show that there is a fully polynomial randomised approximation scheme (FPRAS) for the partition function in the "ferromagnetic" region beta gamma >= 1, but (unless RP=NP) there is no FPRAS in the "antiferromagnetic" region corresponding to the square defined by 0<beta<1 and 0<gamma<1. Neither of these "natural" regions --- neither the hyperbola nor the square --- marks the boundary between tractable and intractable. In one direction, we provide an FPRAS for the partition function within a region which extends well away from the hyperbola. In the other direction, we exhibit two tiny, symmetric, intractable regions extending beyond the antiferromagnetic region. We also extend our results to the asymmetric case mu not equal to 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.