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

Let $[n]:=\lbrace 1, \dots, n \rbrace$. We define a partial ordering on the set of subsets of $[n]$ as follows. We say that $X \preceq Y$ if there is an injective map $f:X \to Y$ such that $x \leq f(x)$ for all $x \in X$. This is a pretty standard construction in poset theory.

The motivation for this question comes from a subset sum problem I've been playing with. Let us regard $[n]$ as the set of indices of a set $A:=\lbrace a_1, \dots, a_n \rbrace$ of numbers (indexed so that $a_1 < \dots < a_n$). If $X \preceq Y$, then the sum of the elements in $A$ corresponding to $X$ is at most the sum of the elements in $A$ corresponding to $Y$. If $X$ and $Y$ are incomparable, then we don't know which sum is bigger (without additional information about $A$).

I would like to cover this poset with as few chains as possible, so it is natural to apply Dilworth's Theorem and then ask

What is the size of a largest antichain in this poset?

One natural candidate is to take all subsets of $[n]$ with the same sum $s$. To maximize the size of this antichain, we should take $s$ to be halfway between $0$ and $1+\dots + n$. I'd guess that this is optimal. Any references or thoughts would be much appreciated.

share|improve this question
    
add comment

1 Answer

up vote 14 down vote accepted

Calling this poset $M(n)$, the fact that it has the Sperner property was conjectured in B. Lindström, "A conjecture on a theorem similar to Sperner's", Combinatorial Structures and Their Applications, p. 241.

It turns out that $M(n)$ has the $k$-Sperner property for all $k$, see R. Stanley's paper "Weyl groups, the hard Lefschetz theorem, and the Sperner property", in the section on the type $B_n$ the properties of $M(n)$ are shown to follow from the general theorems about algebraic posets, the main ingredient being the hard Lefschetz theorem. See also Stanley's article "Some applications of algebra to combinatorics". The papers are available at his website.

share|improve this answer
    
Great! Thanks a lot Gjergji. –  Tony Huynh Oct 6 '11 at 5:23
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.