Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $n$ be a natural number, and consider the discrete cube $2^{[n]} := \{ A: A \subset \{1,\ldots,n\}\}$ consisting of all subsets of the $n$-element set $[n] := \{1,\ldots,n\}$. Define a downset in $2^{[n]}$ to be a collection ${\mathcal D}$ of elements $A$ in $2^{[n]}$ with the property that if $A \in {\mathcal D}$ and $B \subset A$, then $B \in {\mathcal D}$.

My question is: what are the largest and smallest possible values for the alternating sum $\sum_{A \in {\mathcal D}} (-1)^{|A|}$, as ${\mathcal D}$ ranges over downsets in $2^{[n]}$, as a function of $n$? (Here $|A|$ denotes the cardinality of $A$.)

The trivial bounds here are $\pm 2^{n-1}$, by taking only the positive or negative values of ${\mathcal D}$, but of course these values are attained on a "checkerboard" set which is very far from being a downset, and this suggests that significant improvement is possible.

By taking ${\mathcal D}$ to be the set of all subsets $A$ of $2^{[n]}$ of cardinality at most $r$ for some $1 \leq r \leq n-1$, this gives a value of $(-1)^r \binom{n-1}{r}$; setting $r$ close to $(n-1)/2$ then seems to give reasonably good extremals (of size about $2^n/\sqrt{n}$ asymptotically). In the spirit of Sperner's lemma, one might tentatively conjecture that these are the extremal examples, but I was unable to prove or disprove this. (I feel like I'm missing some obvious application of downset isoperimetric inequalities or something.)

One motivation for this question is from analytic number theory: partial divisor sums $\sum_{d|a: d \leq x} \mu(d)$ of the Mobius function (which show up from time to time in this subject) can be viewed as an alternating sum over a downset, where $n$ is the number of prime factors $p_1,\ldots,p_n$ of $a$, and ${\mathcal D}$ is the collection of subsets $A$ of $[n]$ for which $\prod_{i \in A} p_i \leq x$. So any bounds on the general alternating-sum-of-downset problem would imply bounds on partial divisor sums of the Mobius function that depend only on the number of prime factors.

One small observation (using the shifting technology of Frankl) which may or may not be of use: given two natural numbers $1 \leq i < j \leq n$ and a downset ${\mathcal D}$, define the $ij$-shift of ${\mathcal D}$ to be the set formed by replacing any element of ${\mathcal D}$ of the form $A \cup \{j\}$ with $A \cup \{i\}$, if $A$ is disjoint from $\{i,j\}$ and $A \cup \{i\}$ is not already in A. Note that this is again a downset. Call a downset ${\mathcal D}$ shift-minimal if it is equal to all of its $ij$-shifts. Then one can reduce without loss of generality to the shift-minimal case, because shifting does not affect the sum $\sum_{A \in {\mathcal D}} (-1)^{|A|}$. In other contexts, the reduction to the shift-minimal case can be very powerful, but for some strange reason I was unable to exploit it here.

share|improve this question
4  
Possibly related: mathoverflow.net/questions/91712/… (since your sum is the euler characteristic of the down-set). –  Erik Aas Jul 9 '12 at 17:31
1  
@Erik: That does indeed look relevant, in particular the paper of Sagan-Yeh-Ziegler mentioned in David's answer seems to settle the question (at least for the absolute value of the alternating sum) in the case when the downset is an order ideal. It looks like there is now some serious evidence for the tentative conjecture stated above... –  Terry Tao Jul 9 '12 at 17:41
1  
@Terry It looks to me like the definition of a downset is the same as an order ideal. What am I missing? –  David Speyer Jul 9 '12 at 19:39
    
Ah, yes on reading that paper they are using the term "lower order ideal" synonymously with "downset". (In the lattice theory literature, "order ideal" often also requires closure with respect to join, see e.g. en.wikipedia.org/wiki/Ideal_(order_theory) , but that would make the concept trivial in the context of subsets of the cube.) –  Terry Tao Jul 9 '12 at 20:06
    
... huh, it seems I was incorrect on that point: the notion of an "order ideal" is distinct from that of an "order-theoretic ideal"! A bit confusing (and all the more reason to use the terminology "downset", in my opinion...) –  Terry Tao Jul 9 '12 at 20:29
add comment

5 Answers 5

up vote 7 down vote accepted

Thanks for all the very quick responses,they were incredibly useful! Based on these responses, I think the conjecture is now settled in the affirmative, as follows.

For each n, let $F_-(n)$ and $F_+(n)$ be the minimal and maximal values of $\sum_{A \in {\mathcal D}} (-1)^{|A|}$ respectively. The conjecture is that $F_-(n), F_+(n)$ are the extremal values of $(-1)^r \binom{n-1}{r}$ for $r=0,\ldots,n-1$. More explicitly,

$$ F_-(n) = -\binom{n-1}{n/2}, F_+(n) = \binom{n-1}{n/2}$$

when $n$ is even,

$$ F_-(n) = -\binom{n-1}{(n-1)/2}, F_+(n) = \binom{n-1}{(n+1)/2}$$

when $n=3 \mod 4$, and

$$ F_-(n) = -\binom{n-1}{(n+1)/2}, F_+(n) = \binom{n-1}{(n-1)/2}$$

when $n=1 \mod 4$. As mentioned in the post, these bounds would be best possible.

By slicing an n-dimensional downset into two n-1-dimensional downsets, one obtains the inequalities

$$ F_-(n-1)-F_+(n-1) \leq F_-(n) \leq F_+(n) \leq F_+(n-1) - F_-(n-1)$$

which already gives most of the conjecture by induction and Pascal's identity; the only remaining cases that need separate verification are

$$F_+(n) = \binom{n-1}{(n+1)/2} \qquad (1)$$

when n is 3 mod 4, and

$$F_-(n) = -\binom{n-1}{(n+1)/2} \qquad (2)$$

when n is 1 mod 4.

Let's show (1), as the proof of (2) is similar. Fix n equal to 3 mod 4, and let ${\mathcal D}$ be a downset which attains the maximal value $F_+(n)$ of $\sum_{A \in {\mathcal D}} (-1)^{|A|}$:

$$ \sum_{A \in {\mathcal D}} (-1)^{|A|} = F_+(n).$$

Now introduce the "f-vector" $(f_0,\ldots,f_n)$ of $A$, with $f_i := |\{ A \in {\mathcal D}: |A|=i\}|$ defined as the number of elements of ${\mathcal D}$ of cardinality $i$. (This is shifted by one from the polytope conventions, I guess because i points determine an i-1-dimensional simplex.) Then we have

$$ f_0 - f_1 + \ldots - f_n = F_+(n).$$

Let r be the largest index for which $f_r$ is non-zero, or equivalently the largest cardinality of an element of ${\mathcal D}$. (We can treat the degenerate case when ${\mathcal D}$ is empty by hand.) If $r$ was odd, we could simply remove all $r$-element sets from ${\mathcal D}$ and increase the alternating sum, so we may assume that $r$ is even, so the alternating sum looks like $f_0 - f_1 + \ldots - f_{r-1} + f_r$.

The case r=0 can also be treated by hand and will be ignored. Now, we double-count. Observe that each $r$-element set in ${\mathcal D}$ has $r$ "children" as $r-1$-element subsets of ${\mathcal D}$, by removing one of the r elements from that set. On the other hand, each $r-1$-element set can have at most $n-r+1$ "parents", and so

$$ r f_r \leq (n-r+1) f_{r-1}.$$

(EDIT: Actually we didn't need to remove the r=0 case if we adopted the convention $f_{-1}=0$ here.)

In particular, if $r > \frac{n+1}{2}$, then $f_r < f_{r-1}$ we could remove both the r and r-1-element sets from the downset and again increase the sum; so we have $r \leq \frac{n+1}{2}$. In fact the same argument shows that, by changing the extremum ${\mathcal D}$ if necessary, we may assume that $r < \frac{n+1}{2}$, thus (since $n$ is 3 mod 4 and r is even) $r \leq \frac{n-3}{2}$. In other words, every element of ${\mathcal D}$ has cardinality at most $(n-3)/2$.

Now we flip the downset to look at the complementary downset ${\mathcal D}' := \{ A \in [n]: [n] \backslash A \not \in {\mathcal D} \}$. As n is odd, we have $\sum_{A \in {\mathcal D}'} (-1)^{|A|} = \sum_{A \in {\mathcal D}} (-1)^{|A|}$, and so ${\mathcal D}'$ is also an extremiser. Thus, by the above argument, every element of ${\mathcal D}'$ has cardinality at most $(n+1)/2$. Equivalently (as $n$ is odd), ${\mathcal D}$ contains every element of cardinality at most $(n-3)/2$. Combining this with the previous analysis, we see that the extremum is attained at the set consisting precisely of all subsets of [n] of cardinality at most $(n-3)/2$, which gives the required value of $F_+(n)$.

share|improve this answer
    
In retrospect, this would have been a great mini-polymath problem. Ah well. :-) –  Terry Tao Jul 9 '12 at 18:50
1  
Wha do you mean "would have been"? Wasn't it? Also, do I get my Tao number now , or do I have to wait five business days? Gerhard "Happy To Have Rendered Assistance" Paseman, 2012.07.09 –  Gerhard Paseman Jul 9 '12 at 18:59
    
Well, I guess it was in a de facto sense, if not in a premeditated sense. I unfortunately don't have a strong enough application for the bound in order to merit publication, though; I came across the question because I was wondering about how to bound partial divisor sums of the Mobius function, and then felt that it had enough independent interest to pose here, but the bounds don't seem to make any dramatic dents in the bounds for other number-theoretic quantities, alas. But it's still great that the problem seems to be solved, it may be of use at some future date... –  Terry Tao Jul 9 '12 at 19:23
1  
Well, in the meantime, I think I'll submit the sequences F_+ and F_- to OEIS. Whether this will count as a "publication" for the purposes of bibliographic metrics, I leave to the reader. –  Terry Tao Jul 9 '12 at 20:08
2  
I think this question and its solution within 3 hours is a typical example of how much more efficient people can get when collaborating via mathoverflow. –  Christian Stump Jul 10 '12 at 6:41
show 1 more comment

I tried it using linear integer programming for the first few values of $n$, with the following results.

$$ \matrix{ n & min & max\cr 1 & 0 & 1\cr 2 &-1 & 1\cr 3 & -2 & 1\cr 4 & -3 & 3\cr 5 & -4 & 6\cr 6 & -10 & 10\cr 7 & -20 & 15\cr 8 & -35 & 35\cr 9 & -56 & 70\cr} $$

These sequences do not appear to be in the OEIS.

share|improve this answer
    
The bounds for even $n$ look interesting. Does the pattern (i.e. min = - max) continue for further even $n$? –  Michael Albanese Jul 9 '12 at 16:59
    
So far this is consistent with the tentative conjecture proposed above , which more explicitly asserts that the bounds should be $\pm \binom{n-1}{n/2}$ when n is even, between $−\binom{n-1}{(n-1)/2}$ and $\binom{n-1}{(n+1)/2}$ when n is 3 mod 4, and between $-\binom{n-1}{(n+1)/2}$ and $\binom{n-1}{(n-1)/2}$ when n is 1 mod 4. (Thus, for instance, the conjecture would assert -126 and +126 for n=10, -252 and 210 for n=11, and so forth, as both bounds snake down the middle of Pascal's triangle.) –  Terry Tao Jul 9 '12 at 17:29
    
For even $n$ it looks like $\max = -\min = {n \choose {n/2}}/2$, which is obtained taking all the subsets of cardinality $< n/2$ or $> n/2$. –  Robert Israel Jul 9 '12 at 17:31
1  
I can't believe I didn't see this before, but it is trivial that the max and min will be negations of each other in the n even case, because the reflected complement of a downset is again a downset. –  Terry Tao Jul 9 '12 at 17:44
1  
@Gerhard: Nice observation! Indeed, since one can slice an n-dimensional downset into two n-1-dimensional downsets, and the alternating sum of the former is the difference of the two for the latter, I think this shows that the conjecture for even n is implied by the conjecture for n-1, and one of the two bounds for odd n is implied by the bound for n-1. So it's only the smaller of the two bounds in odd n that needs proof... –  Terry Tao Jul 9 '12 at 18:13
show 3 more comments

Here is a simple proof which should give exact optimizers for "most" choices of n mod 4 and max/minimizing; and, near-sharp values for the remaining cases. I'll do it for upsets instead of downsets.

--

Identify the discrete cube with $\{-1,1\}^n$ and let $f : \{-1,1\}^n \to \{0,1\}$ be the indicator of $\mathcal{D}$ which is monotone since $\mathcal{D}$ is an upset. Up to a factor of $2^n$ we are trying to min/maximize $E_x[f(x) \chi(x)]$, where $x$ is uniformly random on the cube and $\chi(x) = \prod_{i=1}^n x_i$. Let $1 \leq j \leq n$ be uniformly random and let $x^{(j)}$ denote $x$ with its $j$th coordinate negated. Since $x^{(j)}$ is also uniformly distributed,

$E_x[f(x) \chi(x)] = E_{x,j}[\frac{f(x) \chi(x) + f(x^{(j)})\chi(x^{(j)})}{2}] = E[\chi(x)\frac{f(x)-f(x^{(j)})}{2}]$

where we used $\chi(x^{(j)}) = -\chi(x)$. Thus in absolute value, the quantity is at most

$E[\bigl|\frac{f(x)-f(x^{(j)})}{2}\bigr|] = \frac{1}{2n}E_x\left[\sum_{i=1}^n \bigl|f(x)-f(x^{(i)})\bigr|\right] = \frac{1}{2n}E\left[\sum_{i=1}^n f(x)x_i\right]$,

where the last step uses that $f$ is monotone. But

$\frac{1}{2n}E\left[\sum_{i=1}^n f(x)x_i\right] = \frac{1}{2n} E\left[f(x)(\sum_{i=1}^n x_i)\right]$

is clearly maximized among $0$-$1$ functions $f$ by the "Hamming ball" which is $1$ when $\sum_{i=1}^n x_i > 0$ and $0$ when $\sum_{i=1}^n x_i < 0$. (If $n$ is even and the sum is $0$, it doesn't matter what $f$'s values are there.)

--

For the purposes of checking sharpness, note that the maximizing $f$ (or $f$'s) there happens to be monotone. The only inequality used is in fact sharp if $n$ is odd and $n$ has the "right" (vis-a-vis min/maxing) remainder mod $4$; if $n$ is even then I think you can get a sharp inequality for any remainder mod $4$ by suitably making $f$ equal to $0$ or $1$ on the middle Hamming layer. I hope a little trick can handle the case of odd $n$ congruent to the "wrong" value mod 4 but I didn't think about it.

--

For people familiar with "analysis of boolean functions", I think this result could be considered "folklore". For example, it essentially appears at the end of page 8 here: http://cs.indstate.edu/~jkinne/research/mon.pdf

share|improve this answer
    
Ah, nice! I had a suspicion that isoperimetric or Sobolev type inequalities must come into play somehow, and one can see them entering in implicitly in this argument... (and also in retrospect, this was clearly a problem for the boolean functions people :-). –  Terry Tao Jul 10 '12 at 5:00
add comment

This is more a comment, but here I have more space:

Did you try to use the characterization of f-vectors of simplicial complexes given by Kruskal in "Joseph B. Kruskal. The number of simplices in a complex. In Mathematical optimization techniques, pages 251–278. Univ. of California Press, Berkeley, Calif., 1963." ?

It states that a vector $(f_{-1},\ldots,f_{d-1})$ is the f-vector of a $d$-dimensional downset if and only if

$$f_{-1} = 1, \quad f_j \leq f_{j-1}^{(j)}, j = 1,\ldots,d-1,$$

where $$a^{(i)} := \binom{a_i}{i+1} + \binom{a_{i-1}}{i} + \ldots + \binom{a_j}{j+1}$$ for the (unique) $i$-canonical expression $$a = \binom{a_i}{i} + \binom{a_{i-1}}{i-1} + \ldots + \binom{a_j}{j}$$ with $a_i > a_{i-1} > \ldots > a_j \geq j \geq 1$.

This might give some insight on min/max values of the alternating sum of f-vectors of downsets.

share|improve this answer
    
Oh, this does look very useful, thanks. Actually, even the more elementary bound $j f_j \leq (d-j+1) f_{j-1}$ coming from double-counting the elements of the downset of cardinality j and j-1 (I may have the normalisations slightly different from your post) may already kill off the problem... I'll have to think about this. –  Terry Tao Jul 9 '12 at 18:16
add comment

I don't know if this will be useful, but the problem can be transformed into a maximum-flow / minimum-cut problem. In fact it's the "strip mining" example in Chvatal, "Linear Programming", pp 372-373. Chvatal refers to J-C Picard, "Maximal closure of a graph and applications to combinatorial problems", Management Science 22 (1976), 1268-1272.

Consider the directed graph consisting of $2^{[n]}$ plus a source $s$ and sink $t$. We have an arc $A\to B$ (of infinite capacity) whenever $B \subset A$. For each subset $A$ of $2^{[n]}$ with even cardinality, we have an arc $s \to A$ with capacity $1$, and for each subset $B$ with odd cardinality, we have an arc $B \to t$ with capacity $1$. Then a minimum cut in this network is $\{s\} \cup \cal D$ where $\cal D$ is a downset maximizing the sum. If instead of $s \to A$ and $B \to t$ we take $A \to t$ and $s \to B$, a minimum cut corresponds to a downset minimizing the sum.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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