If $\Pi_n$ is the set of partitions of $n$, then for $\lambda, \mu\in \Pi_n$ we say $\mu$ dominates $\lambda$ if $\sum\limits_{i=1}^k \lambda_i \leq \sum\limits_{i=1}^k \mu_i$ for all $k$. This gives a partial order on $\Pi_n$ which is not a total order if $n>5$. For example, $(4,1,1)$ and $(3,3)$ are not comparable in $\Pi_6$. This is closely related to the usual ordering on dominant weights in Lie theory.

Question 1: What is the length of a maximal chain in the dominance order on $\Pi_n$? Given the Young diagram for $\lambda$, we get something smaller in the dominance order by moving one square down and to the left in such a way that we get another Young diagram (i.e. applying a simple lowering operator). So this is asking for a longest such "path" from the horizontal Young diagram $(n,0,\ldots,0)\in \Pi_n$ to the vertical Young diagram $(1,1,\ldots, 1,1)\in \Pi_n$.

Question 2: Is there a formula for the number of maximal chains?

  • 1
    $\begingroup$ Do you consider 1,4,1 to be identical to 4,1,1? Are the numbers in non increasing order? $\endgroup$ – Bjørn Kjos-Hanssen Mar 14 '14 at 7:50
  • $\begingroup$ Concerning question 2: do you want to know the number of maximal chains (where maximal is containment order) in the poset, or only the number of chains in the poset of maximal length? $\endgroup$ – Christian Stump Mar 14 '14 at 9:35
  • $\begingroup$ The sequence for all maximal chains starts (for $n \geq 6$) with $4,8,34,182,1733,18547$ and for those of maximial length with $4,4,18,81,1256,2809$. $\endgroup$ – Christian Stump Mar 14 '14 at 9:39
  • $\begingroup$ @Bjorn yes they're in non increasing order $\endgroup$ – user38495 Mar 15 '14 at 15:34
  • $\begingroup$ @Christian I intended to ask for those of maximal length, though maximal chains are interesting too $\endgroup$ – user38495 Mar 15 '14 at 15:35

The longest (descending) chain starts obviously with the partition $n$ having a unique part and ends with the partition $1+1+\dots+1$ into singletons. One should move from $n$ to $1+\dots+1$ by moving dots (unities) down row by row whenever possible along staircases: \begin{eqnarray*}&&n,(n-1)+1,(n-2)+2,(n-2)+1+1,(n-3)+2+1,(n-4)+3+1,\\&&(n-4)+2+2,(n-4)+2+1+1,(n-5)+3+1+1,(n-5)+2+2+1,\\&&(n-6)+3+2+1,(n-7)+4+2+1,\dots\end{eqnarray*} etc. Rule: $\dots+\lambda_k+\lambda_{k+1}+\dots$ moves to $\dots+(\lambda_{k}-1)+ (\lambda_{k+1}+1)+\dots$ if $k$ is the largest index such that $\lambda_{k+1}-\lambda_k\geq 2$ (where $\lambda_{k+1}$ can be zero). If no such $k$ exists, diminish the last maximal part by $1$ moving the dot by the minimal possible amount (such moves are necessary in the lower half of the chain in order to "empty" the staircase). I guess one can get a formula for the length of this chain (which can probably be shown to be of maximal length by an induction argument) in terms of triangular numbers.

The maximal length should be $2{k+1\choose 3}+\alpha k$ where $k$ is maximal such that $n={k+1\choose 2}+\alpha$ with $\alpha\in\{0,\dots,k\}$. (Without stupid mistake on my behalf.) The first values for $n=1,2,\dots$ are $$0,1,2,4,6,8,11,14,17,20,24,28,32,\dots.$$ This is sequence A6463 of the OEIS which mentions that it is the solution to the above problem!

  • $\begingroup$ Okay, you actually did the exercise - nice! $\endgroup$ – Christian Stump Mar 14 '14 at 9:32

This is Exercise 7.2(f) in Stanley "Enumerative Combinatorics II": The length of the longest chain in dominance order is $$\frac{1}{3}m(m^2+3r-1)$$ where $n = \binom{m+1}{2} + r$ with $0 \leq r \leq m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.