The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities

Ijay Narang, Will Perkins

We study approximate counting and sampling algorithms for the hard-core model on $\Delta$-regular bipartite graphs under a spectral expansion condition. Let $M_G$ be the biadjacency mat…