Geodesic
On the shortest sequences of elementary transformations in the partition lattice
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 844-852.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$.
Mots-clés : integer partition
Keywords: lattice, Ferrer's diagram. 
@article{SEMR_2018_15_a70,
     author = {V. A. Baransky and T. A. Senchonok},
     title = {On the shortest sequences of elementary transformations in the partition lattice},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {844--852},
     publisher = {mathdoc},
     volume = {15},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2018_15_a70/}
}
TY  - JOUR
AU  - V. A. Baransky
AU  - T. A. Senchonok
TI  - On the shortest sequences of elementary transformations in the partition lattice
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2018
SP  - 844
EP  - 852
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2018_15_a70/
LA  - ru
ID  - SEMR_2018_15_a70
ER  - 
%0 Journal Article
%A V. A. Baransky
%A T. A. Senchonok
%T On the shortest sequences of elementary transformations in the partition lattice
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2018
%P 844-852
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2018_15_a70/
%G ru
%F SEMR_2018_15_a70
V. A. Baransky; T. A. Senchonok. On the shortest sequences of elementary transformations in the partition lattice. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 844-852. http://geodesic.mathdoc.fr/item/SEMR_2018_15_a70/

[1] M.O. Asanov, V.A. Baransky, V.V. Rasin, Diskretnaya matematika: grafy, matroidy, algoritmy, Lan', SPb, 2010 (In Russian)

[2] G.E. Andrews, The theory of partitions, Cambridge University Press, Cambridge, 1976 | MR

[3] V.A. Baransky, T.A. Koroleva, “The lattice of partitions of a positive integer”, Doklady Math., 77:1 (2008), 72–75 | DOI | MR | Zbl

[4] V.A. Baransky, T.A. Koroleva, T.A. Senchonok, “O reshetke razbieniy natural'nogo chisla”, Trudy Instituta matematiki i mehaniki UrO PAN, 21, no. 3, 2015, 30–36 (In Russian) | MR

[5] V.A. Baransky, T.A. Koroleva, T.A. Senchonok, “On the partition lattice of all integers”, Siberian Electronic Mathematical Reports, 13 (2016), 744–753 | MR | Zbl

[6] T. Brylawski, “The lattice of integer partitions”, Discrete Math, 6 (1973), 210–219 | MR