Skip to main content
edited tags
Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171
edited title
Link
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Alternating sum over collections closed under unioncontainment

added 158 characters in body
Source Link
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Let $\mathscr{C}$ be a collection of subsets of a finite set $P$. Assume $\mathscr{C}$ is closed under unioncontainment: 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}\}|?$$

Let $\mathscr{C}$ be a collection of subsets of a finite set $P$. Assume $\mathscr{C}$ is closed under union. 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}\}|?$$

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

Source Link
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126
Loading