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