Skip to main content
2 of 5
added 142 characters in body
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Alternating sum over collections of sets

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$?

H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126