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

Abstract

A graphical partition is called \emph{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 \emph{height of} $\lambda$ \emph{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$-\emph{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

\begin{enumerate}

\item either $r(\lambda)=r(\mu)-1$, $l(\mathrm{tl}(\mu))<r(\mu)$ or $r(\lambda)=r(\mu)$,

\item $\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|,$

\end{enumerate}

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))<r(\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.