Counting Independent sets in Hypergraphs

Let G be a triangle-free graph with n vertices and average degree t. We prove a lower bound on the number of independent sets G, which is tight up to constants in the exponent. This improves a recent result of Mubayi and Cooper [To appear in Proc. AMS]. This also gives a lower bound for the number of independent sets, independent of the degree.

Further, we prove an upper bound on the number of independent sets in such graphs. We show that for all n, there exists a triangle-free graph with n vertices which has at most exp[(c2+o(1))n\sqrt{\ln n}] independent sets, where c2=1+ln2=1.693147... This disproves a conjecture of Mubayi and Cooper.
We also prove a lower bound on the number of independent sets in linear hypergraphs, which is again tight up to the constant in the exponent. This generalizes a result of Duke, Lefmann, and R\"odl [Rand. Struct. Alg., 95]. Both of our lower bounds follow from a more general statement, which applies to hereditary properties of hypergraphs.

This is joint work with Dhruv Mubayi and Jeff Cooper.