Algorithms for #BIS-hard problems on expander graphs

Matthew Jenssen, Peter Keevash, Will Perkins

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 m…