Sharpened Bonferroni inequalities (Q1204481)

In this paper a \(k\)-uniform hypergraph \(H\) with vertex set \(S\) is said to be sparse if for each \(I\subseteq S\), the induced partial hypergraph \(H_ I=(I,\{e\in E(H)| e\subseteq I\})\) has at most \({| I|- 1\choose k-1}\) edges. The reviewer sharpened Bonferroni inequalities by including an additional term determined by a \(k\)-hypertree \(H\) [J. Comb. Theory, Ser. B 41, 209-217 (1986; Zbl 0577.05052)]. In this paper the author shows that \(H\) need not be a \(k\)-hypertree, but a sparse hypergraph only, a \(k\)-hypertree being a maximal sparse \(k\)-uniform hypergraph since it contains exactly \({| I|-1\choose k-1}\) edges. Knowing that the inequalities hold for a larger class of hypergraphs allows us to find sharper bounds. It is shown that this result is best possible in the sense that the condition on \(H\) is as weak as possible. Similar bounds are given for measures of complemented distributive lattices. No efficient algorithm is known for finding maximal weight sparse hypergraphs; the problem of deciding whether a given hypergraph is sparse may be quite difficult also. Finally, it is shown that there is a class of hypergraphs intermediate between \(k\)-hypertrees and sparse \(k\)- uniform hypergraphs for which the maximization problem can be solved in polynomial time by the greedy algorithm. This is the class of \(k\)-matroid trees, discussed in some detail by the author in [Eur. J. Comb. 12, No. 4, 309-316 (1991; Zbl 0756.05082)].