О максимальных графических разбиениях, ближайших к заданному графическому разбиению

Аннотация

Графическое разбиение называется \emph{максимальным}, если оно максимально по отношению доминирования среди всех графических разбиений заданного веса. Пусть $\lambda$ и $\mu$ --- разбиения такие, что $\mu\leq\lambda$. \emph{Высотой} $\mathrm{height}(\lambda, \mu)$ разбиения $\lambda$ над разбиением $\mu$ называется число преобразований в кратчайшей последовательности элементарных преобразований, преобразующей $\lambda$ в $\mu$. Для заданного графического разбиения $\mu$ максимальное графическое разбиение $\lambda$ такое, что $\mu\leq\lambda$ и $\mathrm{sum}(\mu) = \mathrm{sum}(\lambda)$, называется \emph{ближайшим к $\mu$ по высоте}, если оно имеет минимальную высоту над $\mu$ среди всех максимальных графических разбиений $\lambda'$ таких, что $\mu\leq\lambda'$ и $\mathrm{sum}(\mu) = \mathrm{sum}(\lambda')$. Цель работы состоит в доказательстве следующей теоремы:

Пусть $\mu$ --- графическое разбиение и $\lambda$ --- ближайшее к $\mu$ по высоте максимальное графическое разбиение. Тогда

\begin{enumerate}

\item либо $r(\lambda)=r(\mu)-1$, $l(\mathrm{tl}(\mu))<r(\mu)$, либо $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}

где $r = r(\mu)$ --- ранг, $\mathrm{hd}(\mu)$ --- голова и $\mathrm{tl}(\mu)$ --- хвост разбиения $\mu$, а $l(\mathrm{tl}(\mu))$ --- длина разбиения $\mathrm{tl}(\mu)$.

Мы указываем алгоритм, который порождает некоторое ближайшее к $\mu$ по высоте максимальное графическое разбиение $\lambda$ такое, что $r(\lambda) = r(\mu)$. В случае, когда $l(\mathrm{tl}(\mu)) < r(\mu)$, мы также указываем алгоритм, который порождает некоторое ближайшее к $\mu$ по высоте максимальное графическое разбиение $\lambda$ такое, что $r(\lambda) = r(\mu)-1$.

Попутно мы получили новое доказательство критерия Кохнерта графичности разбиения, которое не использует других критериев графичности разбиений.