Counting almost independent sets in regular graphs

Abstract

Kahn proved that, among bipartite $d$-regular graphs on $n$ vertices, the number of independent sets is maximized by a disjoint union of copies of $K_{d,d}$. Zhao later extended this result to all $d$-regular graphs. We prove a robust version of this theorem in which independent sets are replaced by sets spanning few internal edges. If $G$ is $d$-regular on $n$ vertices, then the number of subsets spanning at most $\gamma dn$ edges is at most $$2^{n/2}\exp \left\{O(\gamma \log (e/\gamma )n)+O(n/d)\right\}.$$ Both correction terms are sharp up to absolute constants: the $\gamma \log (1/\gamma )n$ term is necessary when $d$ is sufficiently large in terms of $\gamma$, while the $n/d$ term is already necessary for independent sets. Our result answers a question of Seth.