Senchonok, T.A., On maximal graphical partitions that are the nearest to a given graphical partition

Abstract

A graphical partition is called maximal if it is maximal under domination among graphical partitions of a given weight. Let λ and μ be partitions such that μ ≤ λ. The height of λ over μ is the number of transformations in some shortest sequence of elementary transformations which transforms λ to μ, denoted by height(λ; μ). For a given graphical partition μ, a maximal graphical partition λ such that μ ≤ λ and sum(μ) = sum(λ) is called the h-nearest to μ if it has the minimal height over μ among all maximal graphical partitions λ' such that μ ≤ λ' and sum(μ) = sum(λ'). The aim is to prove the following result: Let μ be a graphical partition and λ be an h-nearest maximal graphical partition to μ. Then (1) either r(λ) = r(μ)-1, l(tl(μ) < r(μ) or r(λ) = r(μ), (2) height(λ; μ) = height(tl(μ); hd(μ)-[sum(tl(μ)-sum(hd(μ)] = tl(μ)i-hd(μ)i; where r = r(μ) is the rank, hd(μ) is the head and tl(μ) is the tail of the partition μ, l(tl(μ) is the length of tl(μ). We provide an algorithm that generates some h-nearest to μ maximal graphical partition λ such that r(λ) = r(μ). For the case l(tl(μ) < r(μ), we also provide an algorithm that generates some h-nearest to μ maximal graphical partition λ such that r(λ) = r(μ)-1. In addition we present a new proof of the Kohnert's criterion for a partition to be graphical not using other criteria. © 2020 Baransky V.A., Senchonok T.A.