Критерий представления разбиений чисел в виде выпуклой комбинации двух разбиений

Abstract

We study the vertices of the integer partition polytopes. We give a criterion for the problem whether a given partition can be represented as a convex combination of two others. The criterion connects the vertex recognition problem for this polytope with some well-known combinatorial and additive number theory problems, such as the Partition problem from the complexity theory, Sidon sets, and knapsack partitions. We formulate two hypotheses concerning the complexity of the vertex recognition problem, and the behaviour of the vertex number function of the partitioned integer. = Исследуются вершины политопов разбиений чисел. Доказан критерий представления разбиения в виде выпуклой комбинации двух разбиений. Критерий приводит к новым необходимым условиям для вершин и связывает проблему их распознавания с известными вопросами комбинаторики и аддитивной теории чисел: задачей Разбиение, множествами Сидона и рюкзачными разбиениями. Вершины всех политопов разбиений можно рассматривать как мультимножества Сидона смешанного порядка. Они составляют собственный подкласс класса рюкзачных разбиений. Сформулированы предположения о сложности проблемы распознавания вершин и об относительной величине значений функции числа вершин в зависимости от разбиваемого числа.