Counting independent sets in triangle-free graphs

Abstract:

Ajtai, Komlós, and Szemerédi proved that for sufficiently large $t$ every triangle-free graph with $n$ vertices and average degree $t$ has an independent set of size at least $\frac {n}{100t}\log {t}$. We extend this by proving that the number of independent sets in such a graph is at least \[ 2^{\frac {1}{2400}\frac {n}{t}\log ^2{t}}. \] This result is sharp for infinitely many $t,n$ apart from the constant. An easy consequence of our result is that there exists $c’>0$ such that every $n$-vertex triangle-free graph has at least \[ 2^{c’\sqrt n \log n} \] independent sets. We conjecture that the exponent above can be improved to $\sqrt {n}(\log {n})^{3/2}$. This would be sharp by the celebrated result of Kim which shows that the Ramsey number $R(3,k)$ has order of magnitude $k^2/\log k$.