# 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 $$\Sigma = \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\geq l$$? Can one give a non-trivial bound in terms of $$m$$ and $$l$$?

• Is not it the same question? – Fedor Petrov Jul 3 at 13:51
• It would not surprise me if the simplicial complex $\mathscr{S}$ you describe has a name, but I'm not sure how one might google for that... – Sam Hopkins Jul 3 at 14:43
• Well, $\mathbf{P}$ need not be the set of all subsets of $X$ of cardinality $\leq l$. – H A Helfgott Jul 3 at 14:47
• Why a special case? Any contaitment-closed family has such a structure, does not it? – Fedor Petrov Jul 3 at 19:53
• @FedorPetrov: equivalently you are saying any simplicial complex can be realized via this construction. That's plausible but like H.A. I do not see it automatically. – Sam Hopkins Jul 3 at 21:59

Let me try to prove that the question about minimal elements is equivalent to the previous, namely:

Theorem. Assume that $$\mathbf{P}$$ is a finite set and $$\mathscr{S}$$ is a family of subsets of $$\mathbf{P}$$ which is closed under taking over-sets. Then there exists a finite set $$X$$ and an injection $$\varphi:\mathbf{P}\to 2^X$$ such that $$\mathscr{S}=\{\mathbf{S}\subset \mathbf{P}:\cup_{j\in \mathbf{S}}\varphi(j)=X\}.$$

Proof. For any set $$\mathbf{S}\subset \mathbf{P}$$ such that $$\mathbf{S}\notin \mathscr{S}$$ choose an element $$x_{\mathbf{S}}$$ which does not belong to all sets $$\varphi(i),i\in \mathbf{S}$$, and does belong to all $$\varphi(j),j\notin \mathbf{S}$$. Define $$X=\sqcup_{\mathbf{S}} \{x_{\mathbf{S}}\}$$, $$\varphi$$ is already defined. If $$\mathbf{S}\notin \mathscr{S}$$, then $$\cup_{j\in \mathbf{S}}\varphi(j)\ne X$$, because of the element $$x_{\mathbf{S}}$$. Now take $$\mathbf{S}\in \mathscr{S}$$. Fix any element $$x_{\mathbf{T}}\in X$$, where $$\mathbf{T}\notin \mathscr{S}$$. Since all over-sets of $$\mathbf{S}$$ belong to $$\mathscr{S}$$, we conclude that $$\mathbf{T}$$ is not an over-set of $$\mathbf{S}$$, i.e., there exists $$j\in \mathbf{S}\setminus \mathbf{T}$$. The set $$\varphi(j)$$ covers $$x_{\mathbf{T}}$$. Since the element $$x_{\mathbf{T}}\in X$$ was arbitrary, we conclude that $$\cup_{j\in \mathbf{S}}\varphi(j)=X$$.

• I think some complements are missing... – H A Helfgott Jul 3 at 22:58
• I tried my best but still changed $\in$ and $\notin$, hope that now it is ok – Fedor Petrov Jul 3 at 23:44
• OK, I think this works, and disproves that the absolute sum is bounded by the number of minimal sets of $\mathscr{S}$. At the same time, the set $X$ is pretty large (it can be of size $2^{|\mathbf{P}|}$ or close to that), so one can still have a useful bound for this problem (see my answer) and not for the other one. – H A Helfgott Jul 3 at 23:54

The two versions of the problem are fully equivalent. Suppose $$X$$ is a finite set and $$\mathbf{P}$$ is a collection of subsets of $$X$$. Let's define $$f(\mathbf{P})\mathrel{\mathop:}=\sum_{S\in \mathbf{P}}(-1)^{|S|} \qquad \text{and} \qquad g(\mathbf{P})\mathrel{\mathop:}= \sum_{S_1,S_2,\dots,S_r\in \mathbf{P}\\ S_1\cup \cdots \cup S_r=X}(-1)^r.$$ Let's also denote by $$\widehat {\mathbf{P}}$$ the set of all subsets which contain some element of $$\mathbf{P}$$. The following holds: $$g(\mathbf{P})=g(\mathbf{\widehat{\mathbf{P}}})=f(\widehat{\mathbf{P}}).$$ To prove the first equality notice that if $$A_0\subset A_1$$ are subsets such that $$A_0\in \mathbf{P}$$ and $$A_1\notin \mathbf{P}$$ then $$g(\mathbf{P}\cup\{A_1\})-g(\mathbf{P})=\sum_{S_1,S_2,\dots,S_r\in \mathbf{P}\\ A_1\cup S_1\cup \cdots \cup S_r=X}(-1)^{r+1}$$ however the collections that index the sum on the right split into those that contain $$A_0$$ and those that don't. These two cancel each other out and the sum evaluates to zero. Since we can keep adding subsets to $$\mathbf{P}$$ one by one, this shows that $$g(\mathbf{P})=g(\widehat{\mathbf{P}})$$. Finally, the equality $$g(\widehat{\mathbf{P}})=f(\widehat{\mathbf{P}})$$ was proven by Fedor in the previous question (sidenote: this is referred to as Rota's crosscut theorem).

A third equivalent formulation is to ask for bounds on the Euler characteristic of the simplicial complex obtained by using $$X$$ as a set of vertices and adding a simplex for $$S$$ whenever the complement of $$S$$ is in $$\widehat{\mathbf{P}}$$. Thus your questions become:

1. What is the largest Euler characteristic of a simplicial complex with $$N$$ facets?
2. What is the largest Euler characteristic of a simplicial complex with $$N$$ facets and $$m$$ vertices?
3. What is the largest Euler characteristic of a simplicial complex on $$m$$ vertices if all facets have dimension $$\geq m-l$$

The answer to Q1 is $$\binom{N-1}{ \lfloor (N-1)/2 \rfloor}$$ by the Sagan-Yeh-Ziegler paper. They construct a simplicial complex with $$N$$ vertices, $$\binom{N}{\lfloor N/2\rfloor}$$ facets, with Euler characteristic \binom{N-1}{ \lfloor (N-1)/2 \rfloor}, which also gives a simplicial complex with the same Euler characteristic but $$N$$ facets and $$\binom{N}{\lfloor N/2\rfloor}$$ vertices. The answer to Q2 was conjectured to be $$e^{O(\log N\log m)}$$ by David Speyer here, and I don't know what the status of this is.

For Q3, if $$m-l\le \frac{m}{2}$$ then we can use the same example in Q1 which gives the answer $$\binom{m-1}{\lfloor (m-1)/2\rfloor}$$. If $$m-l\geq m/2$$ then the number of facets is at most $$\binom{m}{l}$$ and assuming Speyer's conjecture the correct upper bound should be $$e^{O(\log m \cdot \log \binom{m}{l})}$$.

• I'm confused, isn't the SYZ paper bounding the Euler characteristic of a simplicial complex with a given number of vertices, not facets? – Sam Hopkins Jul 4 at 17:54
• @SamHopkins Yes, it is, but it implies the bound for fixed facets, as mentioned in David's answer I linked to. – Gjergji Zaimi Jul 4 at 17:57
• How do the bound $N\leq \binom{m}{\lfloor m/2\rfloor}$ and the bound $\chi \leq \binom{N-1}{\lfloor (N-1)/2\rfloor}$ imply that $\chi \leq \binom{m-1}{\lfloor (m-1)/2\rfloor}$? I must be missing something. – H A Helfgott Jul 4 at 20:08
• But then $\chi\leq 2^m$ already follows from the trivial bound $f(\widehat{P})\leq |\widehat{P}|\leq 2^m$ and $g(P) = f(\widehat{P})$. – H A Helfgott Jul 4 at 21:42
• Well, $\chi\leq 2^m$ is not in itself obvious, its proof now is elegant, and it's strong enough for me. – H A Helfgott Jul 4 at 21:50

Here's a very naive but arguably non-trivial bound. (Please feel free to do better!)

Just choose a set $$S_0$$ in $$\mathbf{P}$$. It is clear that, for $$\mathbf{S}\subset \mathbf{P}$$ not containing $$S_0$$, if $$\mathbf{S}$$ is in $$\mathscr{S}$$, then the contributions of $$\mathbf{S}$$ and $$\mathbf{S}\cup \{S_0\}$$ to the sum $$\Sigma$$ cancel out. Hence $$\Sigma = - \mathop{\sum_{\mathbf{S}\subset \mathbf{P}}}_{\mathbf{S}\not\in \mathscr{S} \wedge (\mathbf{S}\cup \{S_0\}\in \mathscr{S})} (-1)^{|\mathbf{S}|} = - \sum_{T\subset S_0, T\neq \emptyset}\, \sum_{\mathbf{S}\in \mathscr{S}_{X\setminus T}} (-1)^{|\mathbf{S}|},$$ where, for $$Y\subset X$$, we denote by $$\mathscr{S}_{Y}$$ the set of all subsets $$\mathbf{S}\subset \mathbf{P}$$ such that $$\bigcup_{S\in \mathbf{S}} S = Y$$.

Thus, $$|\Sigma|\leq a_{m,l}$$, where $$a_{m,l}$$ is given by the following recurrence relation: $$a_{m,l} = \sum_{i=1}^{\min(l,m)} \binom{l}{i} a_{m-i,l},$$ with $$a_{0,l}=1$$.

It is easy to show that $$l^m\leq a_{m,l} \leq ((e-1) l)^m$$.

• Have you looked at Moebius inversion on finite posets? My only reference for it is chapter 5 section 7 in " Algebras, Lattices, Varieties". Gerhard "Looking For A Mu Twist" Paseman, 2020.07.03. – Gerhard Paseman Jul 3 at 18:06
• It looks as if it might conceivably be related, but I'm completely unfamiliar with the formalism. Can you see a more precise link? – H A Helfgott Jul 3 at 19:49