Triangle-free graphs with the fewest independent sets

Abstract

Given $d>0$ and a positive integer $n$, let $G$ be a triangle-free graph on $n$ vertices with average degree $d$. With an elegant induction, Shearer (1983) tightened a seminal result of Ajtai, Komlós and Szemerédi (1980/1981) by proving that $G$ contains an independent set of size at least $(1+o(1))\frac{\log d}{d}n$ as $d\to \infty$. By a generalisation of Shearer's method, we prove that the number of independent sets in $G$ must be at least $\exp \left((1+o(1))\frac{(\log d{)}^2}{2d}n\right)$ as $d\to \infty$. This improves upon results of Cooper and Mubayi (2014) and Davies, Jenssen, Perkins, and Roberts (2018). Our method also provides good lower bounds on the independence polynomial of $G$, one of which implies Shearer's result itself. As certified by a classic probabilistic construction, our bound on the number of independent sets is sharp to several leading terms as $d\to \infty$.

12 pages, 1 figure