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