2
$\begingroup$

Given a poset $P$, I am interested in the width (size of the maximal antichain) of $\mathcal{O}(P)$, i.e. the poset of downsets in $P$, ordered by inclusion.

As this is rather difficult, I'm starting with a simplification.

Consider a poset $P$ of $n$ distinct chains (i.e. presented as a product of chains), each of height $h$. Now, what is the size of the maximal antichain of subsets of $P$ that contain exactly one element from each chain? (The ordering we use is that a subset is greater than or equal to another subset if at each chain, it selects an element greater than or equal to that selected by the other poset).

By de Bruijn et al ("On the set of divisors of a number," 1952), I believe this question is the same as asking the maximal rank size of the product of the chains. However, that reformulation does not immediately provide a direct combinatorial formula for the calculation.

Here are some observations I have made thus far:

When $h = 1$, then this reduces to the width of antichains in the powerset of the chains, given by Sperner's theorem as $\binom{n}{\lfloor{n/2}\rfloor}$. Note that these are the central coefficients in the binomial triangle. (i.e. [1,2,3,6,10,20,...])

When $h = 2$, manual calculation of the first few terms leads to the sequence [1,3,7,19], which correspond to central trinomial coefficients.

When $h = 3$, manual calculation of the first few terms leads to the sequence [1,4,12], which seem derivable from higher multinomial formulae.

(some basic reference material is in https://link.springer.com/article/10.1007/BF00396270)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

By the Spernicity and unimodality of a product of chains, the largest size of an antichain in the product of chains of sizes $h_1,\dots,h_d$ is the middle coefficient of the polynomial $\boldsymbol{(h_1)}\cdots\boldsymbol{(h_d)}$, where $$ \boldsymbol{(h)} = 1+x+\cdots+x^{h-1}. $$ See for instance https://core.ac.uk/download/pdf/82798748.pdf. There is no simple formula in general for these middle coefficients.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wow, thanks! Do you know if this particular result is recorded anywhere? The paper gives the setup for deriving it, I see. In addition, do you know of an answer to the original motivating question? When all chains are the same sight, call this middle coefficient m(h,d). My conjecture is that for a poset of width w and height h, the width of the downset is bounded by $\binom{w}{\lfloor{w/2}\rfloor} * m(h,\lceil{w/2}\rceil)$. Is this plausible / in the literature? $\endgroup$
    – Gershom B
    Commented Oct 5, 2019 at 6:23
  • $\begingroup$ Ah, my friend helped me see why this is clearly true. The polynomials come from "striating" posets by sets of chains at each rank level. The two properties ensure that "multiplication works right" and the result still has a meaning as width. Wonderful! $\endgroup$
    – Gershom B
    Commented Oct 11, 2019 at 4:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .