Return to Question

Let $\mathbf{P}$ be a collection of subsets of a finite set $X$. Let $\mathscr{S}$ be the set of all subsets $\mathbf{S}\subset \mathbf{P}$ such that $\bigcup_{S\in \mathbf{S}} S = X$. Can one give a sensible upper bound on the sum $$\sum_{\mathbf{S}\in \mathscr{S}} (-1)^{|\mathbf{S}|},$$ where $|\mathbf{S}|$ is the number of elements of $\mathbf{S}$? In particular: is the absolute value of the sum bounded by the number of minimal elements of $\mathscr{S}$?

(For a strategy that does not work, see Alternating sum over collections closed under containment).

What if every set $S$ in $\mathbf{P}$ is of cardinality $\leq l$, and $|X|=m\geq l$? Can one give a non-trivial bound in terms of $m$ and $l$?

Let $\mathbf{P}$ be a collection of subsets of a finite set $X$. Let $\mathscr{S}$ be the set of all subsets $\mathbf{S}\subset \mathbf{P}$ such that $\bigcup_{S\in \mathbf{S}} S = X$. Can one give a sensible upper bound on the sum $$\Sigma = \sum_{\mathbf{S}\in \mathscr{S}} (-1)^{|\mathbf{S}|},$$ where $|\mathbf{S}|$ is the number of elements of $\mathbf{S}$? In particular: is the absolute value of the sum bounded by the number of minimal elements of $\mathscr{S}$?

(For a strategy that does not work, see Alternating sum over collections closed under containment).

What if every set $S$ in $\mathbf{P}$ is of cardinality $\leq l$, and $|X|=m\geq l$? Can one give a non-trivial bound in terms of $m$ and $l$?

Let $\mathbf{P}$ be a collection of subsets of a finite set $X$. Let $\mathscr{S}$ be the set of all subsets $\mathbf{S}\subset \mathbf{P}$ such that $\bigcup_{S\in \mathbf{S}} S = X$. Can one give a sensible upper bound on the sum $$\sum_{\mathbf{S}\in \mathscr{S}} (-1)^{|\mathbf{S}|},$$ where $|\mathbf{S}|$ is the number of elements of $\mathbf{S}$? In particular: is the absolute value of the sum bounded by the number of minimal elements of $\mathscr{S}$?

(For a strategy that does not work, see Alternating sum over collections closed under containment).

What if every set $S$ in $\mathbf{P}$ is of cardinality $\leq l$, and $|X|=m$? Can one give a non-trivial bound in terms of $m$ and $l$?

Let $\mathbf{P}$ be a collection of subsets of a finite set $X$. Let $\mathscr{S}$ be the set of all subsets $\mathbf{S}\subset \mathbf{P}$ such that $\bigcup_{S\in \mathbf{S}} S = X$. Can one give a sensible upper bound on the sum $$\sum_{\mathbf{S}\in \mathscr{S}} (-1)^{|\mathbf{S}|},$$ where $|\mathbf{S}|$ is the number of elements of $\mathbf{S}$? In particular: is the absolute value of the sum bounded by the number of minimal elements of $\mathscr{S}$?

(For a strategy that does not work, see Alternating sum over collections closed under containment).

What if every set $S$ in $\mathbf{P}$ is of cardinality $\leq l$, and $|X|=m\geq l$? Can one give a non-trivial bound in terms of $m$ and $l$?