On sequences of elementary transformations in the integer partitions lattice

Vitaly A. Baranskii   ; Tatiana A. Senchonok

Ural mathematical journal, Tome 9 (2023) no. 2, pp. 36-45

Résumé

An integer partition, or simply, a partition is a nonincreasing sequence $\lambda = (\lambda_1, \lambda_2, \dots)$ of nonnegative integers that contains only a finite number of nonzero components. The length $\ell(\lambda)$ of a partition $\lambda$ is the number of its nonzero components. For convenience, a partition $\lambda$ will often be written in the form $\lambda=(\lambda_1, \dots, \lambda_t)$, where $t\geq\ell(\lambda)$; i.e., we will omit the zeros, starting from some zero component, not forgetting that the sequence is infinite. Let there be natural numbers $i,j\in\{1,\dots,\ell(\lambda)+1\}$ such that (1) $\lambda_i-1\geq \lambda_{i+1}$; (2) $\lambda_{j-1}\geq \lambda_j+1$; (3) $\lambda_i=\lambda_j+\delta$, where $\delta\geq2$. We will say that the partition $\eta={(\lambda_1, \dots, \lambda_i-1, \dots, \lambda_j+1, \dots, \lambda_n)}$ is obtained from a partition $\lambda=(\lambda_1, \dots, \lambda_i, \dots, \lambda_j, \dots, \lambda_n)$ by an elementary transformation of the first type. Let $\lambda_i-1\geq \lambda_{i+1}$, where $i\leq \ell(\lambda)$. A transformation that replaces $\lambda$ by $\eta=(\lambda_1, \dots, \lambda_{i-1}, \lambda_i-1, \lambda_{i+1}, \dots)$ will be called an elementary transformation of the second type. The authors showed earlier that a partition $\mu$ dominates a partition $\lambda$ if and only if $\lambda$ can be obtained from $\mu$ by a finite number (possibly a zero one) of elementary transformations of the pointed types. Let $\lambda$ and $\mu$ be two arbitrary partitions such that $\mu$ dominates $\lambda$. This work aims to study the shortest sequences of elementary transformations from $\mu$ to $\lambda$. As a result, we have built an algorithm that finds all the shortest sequences of this type.

Détail

Keywords: Ferrers diagram, integer partitions lattice, elementary transformation.
Mots-clés : integer partition

Bibliographie

[1] Andrews G. E., The Theory of Partitions, Cambridge University Press, Cambridge, 1984, 255 pp. | DOI | Zbl

[2] Baransky V. A., Koroleva T. A., Senchonok T. A., “On the partition lattice of an integer”, Trudy Inst. Mat. i Mekh. UrO RAN, 21:3 (2015), 30–36 (in Russian) | MR

[3] Baransky V. A., Koroleva T. A., Senchonok T. A., “On the partition lattice of all integers”, Sib. Electron. Mat. Izv., 13 (2016), 744–753 (in Russian) | DOI | MR | Zbl

[4] Baransky V. A., Senchonok T. A., “On the shortest sequences of elementary transformations in the partition lattice”, Sib. Electron. Mat. Izv., 15 (2018), 844–852 (in Russian) | DOI | MR | Zbl

[5] Baransky V. A., Senchonok T. A., “Bipartite-threshold graphs and lifting rotations of edges in bipartite graphs”, Trudy Inst. Mat. i Mekh. UrO RAN, 29:1 (2023), 24–35 (in Russian) | DOI | MR

[6] Baransky V. A., Senchonok T. A., “Around the Erdös–Gallai criterion”, Ural Math. J., 9:1 (2023), 29–48 | DOI | MR

[7] Brylawski T. The lattice of integer partitions., Discrete Math., 6:3 (1973), 201–219 | DOI | MR | Zbl