Counting independent sets in hypergraphs

Let $G$ be a triangle-free graph with $n$ vertices and average degree $t$. We show that $G$ contains at least $$e^{(1-n^{-1\mathrm{/}12})\frac{1}{2}\frac{n}{t}\ln t(\frac{1}{2}\ln t-1)}$$ independent sets. This improves a recent result of the first and third authors \cite{countingind}. In particular, it implies that as $n\to \mathrm{\infty }$, every triangle-free graph on $n$ vertices has at least $e^{(c_1-o(1))\sqrt{n}\ln n}$ independent sets, where $c_1 = \sqrt{\ln 2}/4 = 0.208138…$\mathrm{.}Further,weshowthatforall$n$, there exists a triangle-free graph with $n$ vertices which has at most $e^{(c_2+o(1))\sqrt{n}\ln n}$ independent sets, where $c_2=1+\ln 2=\mathrm{1.693147..}$. This disproves a conjecture from \cite{countingind}. Let $H$ be a $(k+1)$-uniform linear hypergraph with $n$ vertices and average degree $t$. We also show that there exists a constant $c_k$ such that the number of independent sets in $H$ is at least $$e^{c_k\frac{n}{t^{1\mathrm{/}k}}{\ln }^{1+1\mathrm{/}k}t}\mathrm{.}$$ This is tight apart from the constant $c_k$ and generalizes a result of Duke, Lefmann, and R"odl \cite{uncrowdedrodl}, which guarantees the existence of an independent set of size $\mathrm{\Omega }(\frac{n}{t^{1\mathrm{/}k}}{\ln }^{1\mathrm{/}k}t)$. Both of our lower bounds follow from a more general statement, which applies to hereditary properties of hypergraphs.