Skip to main content
4 of 4
edited tags
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Alternating sum over collections closed under containment

Let $\mathscr{C}$ be a collection of subsets of a finite set $P$. Assume $\mathscr{C}$ is closed under containment: if $S\subset P$ is in $\mathscr{C}$, then every set $S'\subset P$ containing $S$ is in $\mathscr{C}$.

What can we say about $$\sum_{S\in \mathscr{C}} (-1)^{|S|},$$ where $|S|$ is the number of elements of $S$? In particular, is the absolute value of this sum bounded by the number of minimal elements of $\mathscr{C}$, i.e., $$\left|\sum_{S\in \mathscr{C}} (-1)^{|S|}\right| \leq |\{S\in \mathscr{C}:\not \exists S'\subsetneq S \;\text{s.t.}\; S'\in \mathscr{C}\}|?$$

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