RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2018 Volume 15, Pages 844–852 (Mi semr959)

This article is cited in 5 papers

Discrete mathematics and mathematical cybernetics

On the shortest sequences of elementary transformations in the partition lattice

V. A. Baransky, T. A. Senchonok

Ural Federal University, pr. Lenina, 51, 620083, Ekaterinburg, Russia

Abstract: A partition $\lambda= (\lambda_1, \lambda_2, \dots)$ is a sequence of non-negative integers (the parts) in non-increasing order $\lambda_1\geq\lambda_2\geq\dots$ with a finite number of non-zero elements. A weight of $\lambda$ is the sum of parts, denoted by $\mathrm{sum}(\lambda)$. We define two types of elementary transformations of the partition lattice $NPL$. The first one is a box transference, the second one is a box destroying. Note that a partition $\lambda= (\lambda_1, \lambda_2, \dots)$ dominates a partition $\mu= (\mu_1, \mu_2, \dots)$, denoted by $\lambda\geq\mu$, iff $\mu$ is obtained from $\lambda$ by a finite sequence of elementary transformations.
Let $\lambda$ and $\mu$ be two partitions such that $\lambda\geq\mu$. The height of $\lambda$ over $\mu$ is the number of transformations in a shortest sequence of elementary transformations which transforms $\lambda$ to $\mu$, denoted by $\mathrm{height}(\lambda, \mu)$. The aim is to prove that
$$\mathrm{height}(\lambda,\mu)= \sum^\infty_{j=1,\lambda_j>\mu_j}(\lambda_j-\mu_j)= \frac{1}{2}C+\frac{1}{2}\sum^\infty_{j=1}|\lambda_j-\mu_j|,$$
where $C=\mathrm{sum}(\lambda)-\mathrm{sum}(\mu)$. Also we found an algorithm that builds some useful shortest sequences of elementary transformations from $\lambda$ to $\mu$.

Keywords: integer partition, lattice, Ferrer's diagram.

UDC: 519.165

MSC: 05A17

Received June 20, 2018, published August 14, 2018

DOI: 10.17377/semi.2018.15.072



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025