Counting Independent Sets in Hypergraphs. (8th April 2014)

• Record Type: Journal Article
• Authors: COOPER, JEFF; DUTTA, KUNAL; MUBAYI, DHRUV
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 4(2014:Jul.)
• Page Start: 539
• Page End: 550
• Publication Date: 2014-04-08
• Subjects: Primary 05D40, -- Secondary 05C65, -- 05D05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000182
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : Let G be a triangle-free graph with n vertices and average degree t . We show that G contains at least ${\exp\biggl({1-n^{-1/12})\frac{1}{2}\frac{n}{t}\ln t} \biggl(\frac{1}{2}\ln t-1\biggr)\biggr)}$ independent sets. This improves a recent result of the first and third authors [8]. In particular, it implies that as n → ∞, 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 \ldots$ . 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 = 2\sqrt{\ln 2} = 1.665109 \ldots$ . This disproves a conjecture from [8]. Let H be a ( k +1)-uniform linear hypergraph with n vertices and average degree t . We also show that there exists a constant ck such that the number of independent sets in H is at least ${\exp\biggl({c_{k} \frac{n}{t^{1/k}}\ln^{1+1/k}{t}\biggr})}.$ This is tight apart from the constant ck and generalizes a result of Duke, Lefmann and Rödl [9], which guarantees the existence of an independent set of size $\Omega\biggl(\frac{n}{t^{1/k}} \ln^{1/k}t\biggr).$ Both of our lower bounds follow from a more general statement, which applies to hereditary properties of hypergraphs.