|
This article is cited in 5 scientific papers (total 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.
Received June 20, 2018, published August 14, 2018
Citation:
V. A. Baransky, T. A. Senchonok, “On the shortest sequences of elementary transformations in the partition lattice”, Sib. Èlektron. Mat. Izv., 15 (2018), 844–852
Linking options:
https://www.mathnet.ru/eng/semr959 https://www.mathnet.ru/eng/semr/v15/p844
|
Statistics & downloads: |
Abstract page: | 229 | Full-text PDF : | 52 | References: | 24 |
|