We consider natural extremal and algorithmic problems on independent sets in sparse graphs. A conjecture of Khan states that over regular graphs, a disjoint union of complete bipartite graphs maximises the number of independent sets of any given size, and we discuss a proof of this fact for large graphs. The proof also gives an algorithm for approximating the number of independent sets of fixed size in bounded-degree graphs, though the maximum size permitted is not optimal. We then discuss a different approach to this problem that permits larger sizes, and show that the new approach is optimal by identifying a computational phase transition for the problem. Our methods are closely connected to statistical physics. These results comprise joint work with Matthew Jenssen and Will Perkins.