Counting independent sets in triangle-free graphs
Counting independent sets in triangle-free graphs
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 \[ …