Counting independent sets in hypergraphs

Abstract

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/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 \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=\mathrm{0.208138..}$. Further, we show that for all $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/k}}\ln^{1+1/k}{t}}. \] This is tight apart from the constant $c_k$ and generalizes a result of Duke, Lefmann, and Rödl \cite{uncrowdedrodl}, which guarantees the existence of an independent set of size $\Omega (\frac{n}{t^{1/k}}{\ln }^{1/k}t)$. Both of our lower bounds follow from a more general statement, which applies to hereditary properties of hypergraphs.