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

摘要

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 λ 0 such that μ ≤ λ 0 and sum(μ) = sum(λ 0 ). 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(μ)) ? 1 2 [sum(tl(μ)) ? sum(hd(μ))] = 1 2 Pr i=1 |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.