×

Longest chains in the lattice of integer partitions ordered by majorization. (English) Zbl 0605.05003

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)\).
Reviewer: G.Eigenthaler

MSC:

05A17 Combinatorial aspects of partitions of integers
06A06 Partial orders, general
06A15 Galois correspondences, closure operators (in relation to ordered sets)
11P81 Elementary theory of partitions
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Size of largest antichain in partition lattice Par(n).

References:

[1] Brylawski, T., On the lattice of the integer partitions, Discrete Math., 6, 201-219 (1973) · Zbl 0283.06003
[2] Hardy, G. H.; Littlewood, J. E.; Polya, G., (Inequalities (1934), Cambridge University Press: Cambridge University Press London and New York), 1952 · JFM 60.0169.01
[3] Marshall, A. W.; Olkin, I., (Inequalities: Theory of Majorization and its Applications (1979), Academic Press: Academic Press New York) · Zbl 0437.26007
[4] Muirhead, R. F., Some methods applicable to identities and inequalities of symmetric algebraic functions in \(n\) letters, Proc. Edinburgh Math. Soc., 21, 144-157 (1903) · JFM 34.0202.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.