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

• $P = \{1,2,3,4,5,6,7,8\}, \mathscr{C} = \{\emptyset,\{1,2\},\{1,2,3,4\},\{1,2,3,4,5,6\},\{1,2,3,4,5,6,7,8\}\}$ gives $|\sum_{S \in \mathscr{C}} (-1)^{|S|}| = 5$, but the number of minimal elements of $\mathscr{C}$ is $1$. Did I make a mistake? – mathworker21 Jul 2 at 14:18
• No, I did. Let me add a condition. – H A Helfgott Jul 2 at 14:21
• Keywords: "order filter (dually, order ideal) in the Boolean lattice." – Sam Hopkins Jul 2 at 14:27
• It's likely your question has a topological interpretation, via the Mobius function. I think you are essentially asking for the Mobius function of $\hat{0}\cup I \cup \hat{1}$ where $I$ is an order ideal of the Boolean lattice, and asking if it is bounded by the number of maximal elements of $I$. Probably some nice topological property of these posets (e.g. 'shellability') can help you. – Sam Hopkins Jul 2 at 14:33
• – Sam Hopkins Jul 2 at 14:36

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).

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

• It would be interesting to compare this to the bound over all $\mathscr{C}$ from the Sagan-Yeh-Ziegler paper. – Sam Hopkins Jul 2 at 15:20
• it looks that this construction gives an example for about ${m-1\choose \lceil (m-1)/2\rceil}$, do they claim that this is an upper bound also? – Fedor Petrov Jul 2 at 15:31
• Yes, I believe so. – Sam Hopkins Jul 2 at 15:34