Alternating sum over collections closed under containment

Question

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

Answer 1

There is an interpretation of your inequality using simplicial complex and $h$-vector. Namely, let $\Delta$ be the set of all $P-S$ with $S$ in your set. Then $\Delta$ is a collection closed under inclusion, hence a simplicial complex.

The invariant you are interested in is, up to sign, the alternating sum of $f_i$: the number of $i$-dim faces of $\Delta$. Then, by a well-known formula, it is equal to $|h_d|$, where $h_i$ forms the $h$-vector of $\Delta$, and $d-1$ is the dimension of $\Delta$.

The right hand side of the inequality you are interested in is the number of facets (maximal elements) of $\Delta$. As people have pointed out, in general the inequality you want does not hold.

However, I would like to point out that it is likely to hold under certain extra topological/homological assumptions. For instance, if $\Delta$ is Cohen-Macaulay, then all the $h_i$ are non-negative, and the number of facets is $f_{d-1}=\sum_{i\geq 0} h_i\geq h_d$, which is what you need. In fact, as $h_0=1$ and $h_1=n-d$ where $n=|P|$, you get something a little stronger.

One can prove other inequalities for $h_i$ under weaker conditions. For example, if $\Delta$ satisfies Serre's conditions $(S_{r})$, one still have non-negativity of $h_{\leq r}$, a result first proved by Murai-Terai. I discussed some of them in a recent talk (but it is perhaps a bit algebraic).

Answer 2

I am afraid that this inequality does not hold. Let $S_1,\ldots,S_m$ be the minimal elements of $\mathscr{C}=\{S:\exists i\in \{1,\ldots,m\} \, \text{such that}\, S_i\subset S\}$. We have by inclusion-exclusion $$ \sum_{S\in \mathscr{C}} (-1)^S=\sum_{I\subset \{1,\ldots,m\}, I\ne \emptyset} (-1)^{|I|-1}\sum_{T:\cup_{i\in I} S_i\subset T} (-1)^{|T|}. $$ The inner sum equals 0 unless $\cup_{i\in I} S_i=P$, otherwise it equals $(-1)^{|P|}$. Therefore up to sign your sum equals $$ \sum_{I\subset \{1,\ldots,m\}, \cup_{i\in I} S_i=P} (-1)^{|I|-1}. $$ Imagine that the union of any 17 sets from the collection $\{S_1,\ldots,S_m\}$ equals $P$, but the union of no 16 sets $S_i$ equals $P$. This may be achieved by choosing for each 16 sets $S_i$'s a special element which they do not contain, and letting $P$ to be equal to the set of all these elements. Then your sum is some polynomial of degree 16 in $m$.