No label defined (Q4537248)

A finite family \(\{A_v\}_{v\in V}\) of sets is dependent (respectively, independent) [\textit{A. Rényi, C. Rényi} and \textit{J. Surányi}, Sur l'indépendance des domaines simples dans l'espace euclidien à \(n\) dimensions. Colloq. Math. 2, 130-135 (1951; Zbl 0044.04604)] if there exists (respectively, does not exist) a nonempty subset \(X\) of \(V\) such that \(\bigcap_{x\in X}A_x\subseteq\bigcup_{v\notin X}A_v\). Theorem 1. Let \(\{A_v\}_{v\in V}\) be a finite, dependent family of sets. Then there exists a system \({\mathcal J}\) of nonempty, proper subsets of \(V\) such that \(|\bigcup_{v\in V}A_v|=\sum_{I\in{\mathcal J}}(-1)^{|I|-1}|\bigcap_{i\in I}A_i|\). Theorem 1, based on a result in [\textit{K. Dohmen}, An improvement of the inclusion-exclusion principle. Arch. Math. 72, 298-303 (1999; Zbl 0934.05011)], ``immediately gives a result of \textit{D. Q. Naiman} and \textit{H. P. Wynn} [Independence number and the complexity of families of sets. Discrete Math. 154, 203-216 (1996; Zbl 0852.05076)], which states that, for any finite, dependent family of sets \(\{A_v\}_{v\in V}\), there is a system \({\mathcal J}\) of nonempty subsets of \(V\) and a family \(\{c_I\}_{I\in{\mathcal J}}\subseteq {\mathbb{R}}\) such that \(V\notin{\mathcal J}\) and \(|\bigcup_{v\in V}A_v|=\sum_{I\in{\mathcal J}}c_I |\bigcap_{i\in I}A_i|\),'' here with \(c_I=(-1)^{|I|-1}\). Under the requirement that \(|A_1\cup\dots\cup A_n|<2^{n-1}\) a result in \textit{J. Kahn, N. Linial} and \textit{A. Samorodnitsky} [Inclusion-exclusion: Exact and approximate. Combinatorica 16, 465-477 (1996; Zbl 0881.68084)] (cf. \textit{N. Linial} and \textit{N. Nisan} [Approximate inclusion-exclusion. Combinatorica 10, 349-365 (1990; Zbl 0738.05009)]) implies the existence of a system \({\mathcal J}\) of nonempty, proper subsets of \(\{1, 2,\dots,n\}\) such that \(|A_1\cup \dots\cup A_n|\) can be computed using only the intersection sizes \(|\bigcap_{i\in I}A_i |\), where \(I\in{\mathcal J}\). By applying Theorem 1 the author shows, in Theorem 2, that the statement remains valid if the requirement is weakened to \(|A_1\cup\dots\cup A_n|<2^n-1\). An example is provided to show that \({\mathcal J}\) and \(|A_1\cup\dots\cup A_n|\) need not be uniquely determined by the intersection sizes \(|\bigcap_{i\in I}A_i|\) when \(I\neq\{1,\dots, n\}\).