9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $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? $\endgroup$ – mathworker21 Jul 2 at 14:18
  • $\begingroup$ No, I did. Let me add a condition. $\endgroup$ – H A Helfgott Jul 2 at 14:21
  • 2
    $\begingroup$ Keywords: "order filter (dually, order ideal) in the Boolean lattice." $\endgroup$ – Sam Hopkins Jul 2 at 14:27
  • $\begingroup$ 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. $\endgroup$ – Sam Hopkins Jul 2 at 14:33
  • $\begingroup$ See mi.fu-berlin.de/math/groups/discgeom/ziegler/Preprintfiles/… $\endgroup$ – Sam Hopkins Jul 2 at 14:36
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It would be interesting to compare this to the bound over all $\mathscr{C}$ from the Sagan-Yeh-Ziegler paper. $\endgroup$ – Sam Hopkins Jul 2 at 15:20
  • $\begingroup$ 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? $\endgroup$ – Fedor Petrov Jul 2 at 15:31
  • $\begingroup$ Yes, I believe so. $\endgroup$ – Sam Hopkins Jul 2 at 15:34

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.