Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  • 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|improve this question
add comment

1 Answer 1

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