Approximately counting independent sets of a given size in bounded-degree graphs

Abstract

We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density ${\alpha }_c(\Delta )$ and provide (i) for $\alpha <{\alpha }_c(\Delta )$ randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most $\alpha n$ in $n$-vertex graphs of maximum degree $\Delta$; and (ii) a proof that unless NP=RP, no such algorithms exist for $\alpha >{\alpha }_c(\Delta )$. The critical density is the occupancy fraction of the hard core model on the complete graph $K_{\Delta +1}$ at the uniqueness threshold on the infinite $\Delta$-regular tree, giving ${\alpha }_c(\Delta )\sim \frac{e}{1+e}\frac{1}{\Delta }$ as $\Delta \to \infty$. Our methods apply more generally to anti-ferromagnetic 2-spin systems and motivate new questions in extremal combinatorics.