Longest chains in the lattice of integer partitions ordered by majorization (Q1084104): Difference between revisions

The set \(P_ n\) of all partitions \(\lambda =\{\lambda_ 1\geq \lambda_ 2\geq...\}\) of a positive integer n is a lattice with respect to the partial order defined by majorization: \(\mu\leq \lambda\) if and only if \(\lambda_ 1+...+\lambda_ i\geq \mu_ 1+...+\mu_ i\) for all positive integers i. The lattice \((P_ n,\leq)\) is self-dual and fails to have a rank function. For \(\mu\leq \lambda\), the height h(\(\mu\),\(\lambda)\) is defined to be the length of the longest chain from \(\mu\) to \(\lambda\). In this paper, an algorithmic description of a certain natural type of maximal chains between \(\mu\leq \lambda\) (called ''HV-chains from \(\lambda\) to \(\mu\) '') is given. In these HV-chains covers of a certain kind (called ''H-steps'') precede covers of another kind (called ''V-steps''). The main result is that all HV-chains from \(\lambda\) to \(\mu\) have the same length, and this length is h(\(\mu\),\(\lambda)\).