English
!

Доклады

Число вершин политопа разбиений чисел: результаты и гипотезы

Шлык В.А.

Белорусский государственный университет, Республика Беларусь, 220030, Минск, пр. Независимости 4, 375172095049; Университет гражданской защиты МЧС Беларуси, Республика Беларусь, 220118, Минск, ул. Машиностроителей 25, +375291716928 v.shlyk@gmail.com

Разбиения чисел составляют предмет классического направления в теории чисел и комбинаторике. Предложенный автором полиэдральный подход в теории разбиений основан на рассмотрении множества разбиений каждого числа n в виде политопа [1], выпуклой оболочки соответствующих целых точек в n-мерном пространстве. Особенно важны вершины политопа и их число, так как каждое разбиение является выпуклой комбинацией вершин. Критерий распознавания вершин до сих пор неизвестен.

Вычисление вершин для n ≤ 105 показало, что их число возрастает не монотонно: для четного n оно меньше, чем для n-1, а самые высокие пики угадываются для простых n. Мы объясняем пилообразный вид функции числа вершин большим числом разбиений четных n, впервые вычисленным Метрополисом и Штейном [2]. Разбиения Метрополиса являются выпуклыми комбинациями двух разбиений и бόльшая часть разбиений принадлежит этому классу. Показано, что для n кратных 3 число вершин также уменьшается. Это, по-видимому, вызвано большим количеством разбиений, являющихся выпуклыми комбинациями трех, но не двух разбиений. Охарактеризованы коэффициенты в таких представлениях целых точек произвольного целочисленного политопа. Чтобы исследовать феномен простых n, мы классифицируем целые числа по их, в определенном смысле, близости к простым и визуально показываем, что график функции числа вершин распадается на слои, соответствующие введенным классам. Основная гипотеза утверждает, что число вершин зависит от малых делителей n.

Обнаруженная зависимость числа вершин политопа разбиений от мультипликативных свойств разбиваемого числа приводит к новым интересным проблемам. Одна из них связана с опорными вершинами, составляющими базис множества вершин относительно введенных ранее двух комбинаторных операций.

Приведены свидетельства того, что аналогичное расслоение имеет место для функции числа вершин углового многогранника Гомори на циклической группе, играющего ключевую роль в целочисленном программировании.

Литература

1. Shlyk V.A. Polytopes of partitions of numbers // European Journal of Combinatorics 26, 2005. С. 1139-1153.

2. Metropolis N., Stein P.R. An elementary solution to a problem in restricted partitions // Journal of Combinatorial Theory 9, 1970. P. 365-376.

© 2004 Дизайн Лицея Информационных технологий №1533