Sharpened Bonferroni inequalities
type: Item
instance of: scholarly article
title: Sharpened Bonferroni inequalities
zbMATH Open document ID: 0772.05074
author: David A. Grable
published in: Journal of Combinatorial Theory. Series B
publication date: 1993-03-10T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A20
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 130575
zbMATH Keywords: \(k\)-uniform hypergraphs
zbMATH Keywords: \(k\)-matroid trees
zbMATH Keywords: Bonferroni inequalities
zbMATH Keywords: sparse hypergraph
zbMATH Keywords: greedy algorithm
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
full work available at URL: jctb.1993.1011
OpenAlex ID: W1982553982
DOI: 10.1006/JCTB.1993.1011
description: scientific article; zbMATH DE number 130575