  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.

Data Structures and Algorithms;Computational Complexity;Combinatorics