On maximal graphical partitions that are the nearest to a given graphical partition

V. A. Baransky ; T. A. Senchonok

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 338-363

Résumé

A graphical partition is called maximal if it is maximal under domination among graphical partitions of a given weight. Let $\lambda$ and $\mu$ be partitions such that $\mu\leq\lambda$. The height of $\lambda$ over $\mu$ is the number of transformations in some shortest sequence of elementary transformations which transforms $\lambda$ to $\mu$, denoted by $\mathrm{height}(\lambda,\mu)$. For a given graphical partition $\mu$, a maximal graphical partition $\lambda$ such that $\mu\leq\lambda$ and $\mathrm{sum}(\mu)= \mathrm{sum}(\lambda)$ is called the $h$-nearest to $\mu$ if it has the minimal height over $\mu$ among all maximal graphical partitions $\lambda'$ such that $\mu\leq\lambda'$ and $\mathrm{sum}(\mu)= \mathrm{sum}(\lambda')$. The aim is to prove the following result: Let $\mu$ be a graphical partition and $\lambda$ be an $h$-nearest maximal graphical partition to $\mu$. Then either $r(\lambda)=r(\mu)-1$, $l(\mathrm{tl}(\mu))$ or $r(\lambda)=r(\mu)$, $\mathrm{height}(\lambda,\mu)= \mathrm{height}(\mathrm{tl}(\mu), \mathrm{hd}(\mu))- \frac{1}{2}[\mathrm{sum}(\mathrm{tl}(\mu))-\mathrm{sum}(\mathrm{hd}(\mu))]= \frac{1}{2}\sum^r_{i=1}|\mathrm{tl}(\mu)_i-\mathrm{hd}(\mu)_i|,$ where $r=r(\mu)$ is the rank, $\mathrm{hd}(\mu))$ is the head and $\mathrm{tl}(\mu))$ is the tail of the partition $\mu$, $l(\mathrm{tl}(\mu))$ is the length of $\mathrm{tl}(\mu)$. We provide an algorithm that generates some $h$-nearest to $\mu$ maximal graphical partition $\lambda$ such that $r(\lambda)=r(\mu)$. For the case $l(\mathrm{tl}(\mu))$, we also provide an algorithm that generates some $h$-nearest to $\mu$ maximal graphical partition $\lambda$ such that $r(\lambda)=r(\mu)-1$. In addition we present a new proof of the Kohnert's criterion for a partition to be graphical not using other criteria.

Détail

Keywords: threshold graphs, lattice of integer partitions, graphical partition, maximal graphical partition, Ferrer's diagram.