MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
See also this question: – Russ Woodroofe Jan 23 '14 at 19:25
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|cite|improve this answer
Great! Thanks a lot Gjergji. – Tony Huynh Oct 6 '11 at 5:23

Your Answer


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.