Alternating sum over collections of sets

Question

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

Answer 1

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

Answer 2

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

Answer 3

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