2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Is not it the same question? $\endgroup$ – Fedor Petrov Jul 3 at 13:51
  • 1
    $\begingroup$ 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... $\endgroup$ – Sam Hopkins Jul 3 at 14:43
  • 1
    $\begingroup$ Well, $\mathbf{P}$ need not be the set of all subsets of $X$ of cardinality $\leq l$. $\endgroup$ – H A Helfgott Jul 3 at 14:47
  • 2
    $\begingroup$ Why a special case? Any contaitment-closed family has such a structure, does not it? $\endgroup$ – Fedor Petrov Jul 3 at 19:53
  • 1
    $\begingroup$ @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. $\endgroup$ – Sam Hopkins Jul 3 at 21:59
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think some complements are missing... $\endgroup$ – H A Helfgott Jul 3 at 22:58
  • $\begingroup$ I tried my best but still changed $\in$ and $\notin$, hope that now it is ok $\endgroup$ – Fedor Petrov Jul 3 at 23:44
  • $\begingroup$ 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. $\endgroup$ – H A Helfgott Jul 3 at 23:54
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm confused, isn't the SYZ paper bounding the Euler characteristic of a simplicial complex with a given number of vertices, not facets? $\endgroup$ – Sam Hopkins Jul 4 at 17:54
  • 1
    $\begingroup$ @SamHopkins Yes, it is, but it implies the bound for fixed facets, as mentioned in David's answer I linked to. $\endgroup$ – Gjergji Zaimi Jul 4 at 17:57
  • $\begingroup$ 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. $\endgroup$ – H A Helfgott Jul 4 at 20:08
  • 1
    $\begingroup$ 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})$. $\endgroup$ – H A Helfgott Jul 4 at 21:42
  • 1
    $\begingroup$ Well, $\chi\leq 2^m$ is not in itself obvious, its proof now is elegant, and it's strong enough for me. $\endgroup$ – H A Helfgott Jul 4 at 21:50
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jul 3 at 18:06
  • $\begingroup$ It looks as if it might conceivably be related, but I'm completely unfamiliar with the formalism. Can you see a more precise link? $\endgroup$ – H A Helfgott Jul 3 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.