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 ?_c(?) and provide (i) for ? ?_c(?). The critical density is the occupancy fraction of hard core model on the clique K_{?+1} at the uniqueness threshold on the infinite ?-regular tree, giving ?_c(?) ~ e/(1+e)1/(?) as ? ? ?