APPROXIMATELY COUNTING INDEPENDENT SETS OF A GIVEN SIZE IN BOUNDED-DEGREE GRAPHS

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) similar to e/1+e 1/Delta as Delta -> infinity. Our methods apply more generally to antiferromagnetic 2-spin systems and motivate new questions in extremal combinatorics.