Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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
  • Write $E_k = (\{0, \ldots, k-1\}, \leq)$ the total order on $k$ elements.
  • If $(A, \leq_A)$ and $(B, \leq_B)$ are two posets, the product poset is $(A \times B, \leq_{A \times B})$ with the order defined by $(a, b) \leq_{A \times B} (a', b')$ iff $a \leq_A a'$ and $b \leq_B b'$. This product is associative.
  • An antichain of a poset $(X, \leq)$ is a subset $A \subseteq X$ such that all elements of $A$ are pairwise incomparable. The width of a poset is the cardinality of its largest antichain.

Given $x_1, \ldots, x_n$, what is the width of $E_{x_1} \times \cdots \times E_{x_n}$?

Simple examples: the width of $E_k$ is $1$ for any $k$, the width of $E_k^2$ is $k$ (becasue $\{(0, k), (1, k-1), \ldots, (k, 0)\}$ is an antichain and the pidgeonhole principle ensures that a larger subset would necessarily contain two comparable elements).

share|cite|improve this question
up vote 2 down vote accepted

This is an answer, but it’s not a very nice one.

A finite chain is trivially a graded, rank-symmetric, rank-unimodal partial order with the Sperner property.

A partial order $\langle P,\le\rangle$ is graded of rank $m$ if there is a rank function $r:P\to\{0,\dots,m\}$ such that $r(p)=0$ for each minimal element $p$ of $P$, and $r(q)=r(p)+1$ iff $q$ covers $p$, i.e., $p<q$, and there is no $r\in P$ such that $p<r<q$. Your $E_n$ is graded of rank $n-1$ by the function $r(k)=k$. For $k=0,\dots,m$ let $P_k=\{p\in P:r(p)=k\}$; $P$ is rank-symmetric if $|P_k|=|P_{m-k}|$ for $k=0,\dots,m$. Finally, $P$ is rank-unimodal if the sequence $\big\langle|P_0|,|P_1|,\dots,|P_m|\big\rangle$ is unimodal.

It is known that if $P$ and $Q$ are graded, rank-symmetric, rank-unimodal, finite partial orders with the Sperner property, then so is $P\times Q$. I don’t know the original source of this result, but a proof can be found in this paper.

Let $P=E_{n_1}\times\ldots\times E_{n_r}$ for some $n_1,\dots,n_r\in\Bbb Z^+$, and assume without loss of generality that $n_1\le\ldots\le n_r$. For any $m$ let

$$A_m=\left\{\langle a_1,\dots,a_r\rangle\in P:\sum_{k=1}^ra_k=m\right\}\;;$$

then $A_m=\{a\in P:r(a)=m\}$, where $r$ is the rank function, and it’s easy to see that $A$ is an antichain in $P$. Since $P$ has the Sperner property, its width (maximum size of an antichain in $P$) is $\max_m|A_m|$.

$|A_m|$ is the number of solutions of $$x_1+\ldots+x_r=m\tag{1}$$ in non-negative integers subject to the condition that $x_k\le n_k-1$ for $k=1,\dots,r$. This can be calculated by a combination of stars-and-bars calculations and an inclusion-exclusion argument.

Let $[r]^k$ be the set of $k$-element subsets of $\{1,\dots,r\}$. For a fixed $S\in[r]^k$, the number of solutions to $(1)$ that violate the upper bounds on each $x_i$ for $i\in S$ is (by the stars-and-bars formula)

$$\binom{m+r-1-\displaystyle\sum_{i\in S}n_i}{r-1}\;,$$

so the usual inclusion-exclusion calculation yields

$$|A_m|=\sum_{k=0}^r(-1)^k\sum_{S\in[r]^k}\binom{m+r-1-\displaystyle\sum_{i\in S}n_i}{r-1}\;.$$

(For a slighly more detailed exposition in an answer to a similar problem, see here.) I don’t know of any simplification of this for arbitrary $n_k$.

The problem remains to determine what value of $m$ will maximize $|A_m|$. The maximum element of $P$ is $\langle n_1-1,\dots,n_r-1\rangle$, with rank $\sum_{k=1}^rn_k-r$. $P$ is rank-symmetric, $|A_m|$ is maximal if $$m=\left\lfloor\frac12\left(\sum_{k=1}^rn_k-r\right)\right\rfloor\;.$$

share|cite|improve this answer
Thanks a lot for this detailed answer! Is this new, or are those results from an existing source? – a3nm Feb 12 '13 at 10:24
@a3nm: You’re welcome! The Sperner property was new to me $-$ this isn’t my field at all $-$ but it seems to be quite well studied; searching on it will turn up quite a bit, as will searching on graded poset, graded partial order, etc. The actual calculations are mine, though I expect that others have done them; I just wouldn’t have any idea where to look! – Brian M. Scott Feb 12 '13 at 10:29

This is another related paper:

Jerrold R. Griggs Maximum antichains in the product of chains.

share|cite|improve this answer
Thanks! As far as I can see, this paper points out that a product of chains has the Sperner property, and then is concerned about which products have the strict Sperner property, i.e., all their maximal antichains correspond to a rank. I don't think it does any estimation of the width itself, which @Brian M. Scott did in his answer. – a3nm Mar 26 at 8:19
I don't have enough reputation to comment on the previous answer. I am doing some numerical evaluation, from which I think the sum should go only to $r-1$, not to $r$. – Andrea Censi Mar 26 at 15:14
Which sum of are you referring to? Is it the last one? Then could you explain a bit why it should only go to $r-1$? (From my understanding, you should sum across all the $r$ chains.) – a3nm Mar 28 at 8: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.