We study the connection between the correlation decay property (more precisely, strong spatial mixing) and the zerofreeness of the partition function of 2spin systems on graphs of bounded degree. We show that for 2spin systems on an entire family of graphs of a given bounded degree, the
 Publication Date:
 NSFPAR ID:
 10308264
 Journal Name:
 Journal of Statistical Physics
 Volume:
 185
 Issue:
 2
 ISSN:
 00224715
 Publisher:
 Springer Science + Business Media
 Sponsoring Org:
 National Science Foundation
More Like this

We study the problem of approximating the value of the matching polynomial on graphs with edge parameter γ, where γ takes arbitrary values in the complex plane. When γ is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of γ, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree Δ as long as γ is not a negative real number less than or equal to −1/(4(Δ −1)). Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all Δ ≥ 3 and all real γ less than −1/(4(Δ −1)), the problem of approximating the value of the matching polynomial on graphs of maximum degree Δ with edge parameter γ is #Phard. We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real γ, it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this resultmore »

Chawla, Shuchi (Ed.)Understanding the complexity of approximately counting the number of weighted or unweighted independent sets in a bipartite graph (#BIS) is a central open problem in the field of approximate counting. Here we consider a subclass of this problem and give an FPTAS for approximating the partition function of the hardcore model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the sides (L, R) of the bipartition. This includes, among others, the biregular case when λ = 1 (approximating the number of independent sets of G) and Delta_R >= 7 Delta_L log(Delta_L). Our approximation algorithm is based on truncating the cluster expansion of a polymer model partition function that expresses the hardcore partition function in terms of deviations from independent sets that are empty on one side of the bipartition. Further consequences of this method for unbalanced bipartite graphs include an efficient sampling algorithm for the hardcore model and zerofreeness results for the partition function with complex fugacities. By utilizing connections between the cluster expansion and joint cumulants of certain random variables, we go beyond previous algorithmic applications of the cluster expansion to prove that the hardcore model exhibits exponential decay of correlations for allmore »

Abstract Unlike their fermionic counterparts, the dynamics of Hermitian quadratic bosonic Hamiltonians are governed by a generally nonHermitian Bogoliubovde Gennes effective Hamiltonian. This underlying nonHermiticity gives rise to a
dynamically stable regime, whereby all observables undergo bounded evolution in time, and adynamically unstable one, whereby evolution is unbounded for at least some observables. We show that stabilitytoinstability transitions may be classified in terms of a suitablygeneralized $\mathcal{P}\mathcal{T}$symmetry , which can be broken when diagonalizability is lost at exceptional points in parameter space, but also when degenerate real eigenvalues split off the real axis while the system remains diagonalizable. By leveraging tools from Krein stability theory in indefinite innerproduct spaces, we introduce an indicator of stability phase transitions, which naturally extends the notion of phase rigidity from nonHermitian quantum mechanics to the bosonic setting. As a paradigmatic example, we fully characterize the stability phase diagram of a bosonic analogue to the Kitaev–Majorana chain under a wide class of boundary conditions. In particular, we establish a connection between phasedependent transport properties and the onset of instability, and argue that stable regions in parameter space become of measure zero in the thermodynamic limit. Our analysis also reveals that boundary conditions that supportmore » 
We present a quasipolynomial time classical algorithm that estimates the partition function of quantum manybody systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NPhard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factor of logn to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum manybody systems.

Abstract Partitioning networks into communities of densely connected nodes is an important tool used widely across different applications, with numerous methods and software packages available for community detection. Modularitybased methods require parameters to be selected (or assume defaults) to control the resolution and, in multilayer networks, interlayer coupling. Meanwhile, most useful algorithms are heuristics yielding different nearoptimal results upon repeated runs (even at the same parameters). To address these difficulties, we combine recent developments into a simpletouse framework for pruning a set of partitions to a subset that are selfconsistent by an equivalence with the objective function for inference of a degreecorrected planted partition stochastic block model (SBM). Importantly, this combined framework reduces some of the problems associated with the stochasticity that is inherent in the use of heuristics for optimizing modularity. In our examples, the pruning typically highlights only a small number of partitions that are fixed points of the corresponding map on the set of somewhereoptimal partitions in the parameter space. We also derive resolution parameter upper bounds for fitting a constrained SBM of
K blocks and demonstrate that these bounds hold in practice, further guiding parameter space regions to consider. With publicly available code (http://github.com/ragibson/ModularityPruning ), our pruningmore »