Algorithms for #BIS-Hard Problems on Expander Graphs
Matthew Jenssen, Peter Keevash, Will Perkins
Abstract
We give a fully polynomial-time approximation scheme (FPTAS) and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) Δ-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the nonuniqueness regime of the infinite Δ-regular tree. We also find efficient counting and sampling algorithms for proper -colorings of random Δ-regular bipartite graphs when is sufficiently small as a function of Δ.
Topics & Concepts
Bipartite graphExpander graphMathematicsCombinatoricsBounded functionDegree (music)Discrete mathematicsIsing modelRandom graphPotts modelApproximation algorithmGraphStatistical physicsMathematical analysisPhysicsAcousticsMarkov Chains and Monte Carlo MethodsStochastic processes and statistical mechanicsTheoretical and Computational Physics