Width of a certain poset

232 Views Asked by At

Define the poset $C_n=\langle \{1,2,\ldots,n\},\leq \rangle$. Do we have any single formula on the width of $C_n\times C_n\times C_n \times \ldots \times C_n$ where $\times$ is the direct product, and there are $m$ $C_n$s.

1

There are 1 best solutions below

4
On BEST ANSWER

By a theorem of de Bruijn, Tengbergen and Kruyswijk, one antichain of maximal size in a product of chains is those points at the "middle level". Here the level of a point $(a_1,\ldots,a_m)$ will be $a_1+\cdots+a_m-m$ and the maximum level is $m(n-1)$. So the width will be the number of solutions to $$a_1+ \cdots +a_m -m =\left\lfloor\frac{m(n-1)}2\right\rfloor$$ for integers $a_i\in\{1,\ldots,n\}$. Now what this number is, I don't know.

A reference for the theorem of de Bruijn, Tengbergen and Kruyswijk is Ian Anderson's book Combinatorics of Finite Sets.