Algorithms for #BIS-hard problems on expander graphs

2018/07/12 by Matthew Jenssen, Peter Keevash, Jenssen, Matthew +3
Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1807.04804

openalex publication_date 2018/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an 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 non-uniqueness regime of the infinite Δ-regular tree. We also find efficient counting and sampling algorithms for proper q-colorings of random Δ-regular bipartite graphs when q is sufficiently small as a function of Δ.

Related

• Efficient algorithms for the Potts model on small-set expanders
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Approximately counting independent sets of a given size in bounded-degree graphs
• The computational hardness of counting in two-spin models on d-regular graphs
• Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs