Inapproximability of Counting Independent Sets in Linear Hypergraphs

Guoliang Qiu, Jiaheng Wang

It is shown in this note that approximating the number of independent sets in a $k$-uniform linear hypergraph with maximum degree at most $\Delta$ is NP-hard if $\Delta \ge 5\cdot 2^{k-1}+1$…