Width of a product of chains

Question

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

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\;.$$