🗊Презентация Вершины политопа числа разбиений

Вершины политопа числа разбиений

Введение Всякое представление положительного целого числа n в виде суммы положительных целых чисел без учета их порядка называется разбиением числа: n = i1 + i2+ … + ik, 1 ≤ i1, i2, … ik ≤ n В данной работе используется полиэдральный подход к разбиениям чисел. Он заключается в том, что каждому разбиению числа n будет ставиться в соответствие вектор из , где i-ая координата вектора, говорит сколько раз часть размера i входит в разбиение. Например, разбиению 7 = 1 + 2 + 1 + 3 соответствует вектор x = (2,1,1,0,0,0,0). Вектор x можем называть разбиением. Рассматривая все разбиения как вектора, можно получить политоп разбиений, путем выпуклой оболочки всех векторов разбиений. Исследование некоторых свойств этого политопа проведено в данной работе.

Цели работы Исследовать способ нахождения сопряженных разбиений 2. Сформулировать и доказать теорему о лифтинге вершин 3. Доказать теорему Шлыка для опорных вершин, сформулировать и доказать теорему о лифтинге опорных вершин.

Основные теоретические понятия для нахождения сопряженных разбиений Граф Феррера. Графическое представление разбиения. Любой граф Феррера является разбиением и наоборот. Сопряженное разбиение. Проведя главную диагональ в графе Феррера, проведем его транспонирование (операция сопряжения). Полученное разбиение называется сопряженным. Оператор Вонга. Матрица следующего вида размеров n x n :

Нахождение сопряженных разбиений Введем операцию пересмотра : вектор x = (2,1,1,0,0,0,0) будем рассматривать как следующее разбиение 2+1+1+0+0+0+0=4. Теорема. Оператор Вонга с последующей ему операцией пересмотра переводит разбиение числа в сопряженное ему разбиение, то есть последовательное их применение является операцией сопряжения.

Критерий вершины и опорные вершины Критерий вершины. Точка n∈ , принадлежащая некоторому политопу P ⊂ , является его вершиной тогда и только тогда, когда ее нельзя представить в виде выпуклой комбинации x = j λj y j,j λj = 1, λj > 0, некоторых других точек y j ∈ P, 1 ≤ j ≤ k. Это относится и к политопу разбиений Pn . Для введения опорных вершин, понадобятся операции укрупнения частей. Операция 1. Берем части размеров u,v. Пусть число частей u = a меньше числа частей v = b. Соединяем a частей размера u с a частями размера v, получая a частей u+v. Операция 2. Соединяем все части одного размера в новую часть, число соединяемых частей больше 1. Строгое определение операций укрупнения частей представлено в работе. Определение. Опорной вершиной называется такая вершина политопа Pn , если ее нельзя получить в результате применения операций укрупнения частей к какой-либо другой вершине этого политопа.

Лифтинг вершин Теорема Шлыка. Пусть x ⊢ n и x ∈ vert Pn . Если из разбиения x удалить часть размера i ∈ S(x), то есть сделать из вектора x=(x1,..., xi-1, xi, xi+1,..., xn),где xi =1,вектор y=(x1,..., xi-1, xi -1, xi+1,..., xn), то вектор y будет вершиной политопа Pn-i. Теорема (о лифтинге вершин). Пусть x ⊢ n и x ∈ vertPn , тогда если к разбиению x добавить : часть размера i, где i ≠ n, i > n, то полученное разбиение y=(x1,...,xn,...,xi-1,xi+1,xi+1,...,xn+i) будет являться вершиной политопа разбиений числа n+i, xj=0, j>n часть размера i∈S(x), где n/2 < i < n, то полученное разбиение y=(x1,...xi-1,xi+1,xi+1,...,xn,...,xn+i) будет являться вершиной политопа разбиений числа n+i, xj=0, j>n

На основе теоремы о лифтинге были получены следующие результаты для нижней границы количества вершин, которые можно вычислить с помощью этой теоремы. n - число, чей политоп рассматривается ; h - [n/2] с округлением вверх ; v(n) - число вершин политопа разбиений n ; t - нижняя граница для количества вершин, которые можно вычислить с помощью теоремы о лифтинге вершин На основе теоремы о лифтинге были получены следующие результаты для нижней границы количества вершин, которые можно вычислить с помощью этой теоремы. n - число, чей политоп рассматривается ; h - [n/2] с округлением вверх ; v(n) - число вершин политопа разбиений n ; t - нижняя граница для количества вершин, которые можно вычислить с помощью теоремы о лифтинге вершин

Теорема Шлыка для опорных вершин и лифтинг опорных вершин Теорема Шлыка (для опорных вершин). Пусть x ⊢ n и x∈ sup.vert Pn. Если из разбиения x удалить часть размера i∈S(x), где n/2<i, то есть сделать из вектора x=(x1,...,xi-1,xi,xi+1,...,xn), где xi =1, вектор y=(x1,...,xi-1,xi -1,xi+1,...,xn).Тогда вектор y будет опорной вершиной политопа Pn-i. Теорема (о лифтинге опорных вершин). Пусть x ⊢ n и x∈ sup.vert Pn. Если к разбиению x добавить часть размера i∈S(x), где n/2<i, то есть сделать из вектора x=(x1,...,xi-1,xi,xi+1,...,xn), где xi =1, вектор y=(x1,...,xi-1,xi +1,xi+1,...,xn). Тогда вектор y будет опорной вершиной политопа Pn+i.

Спасибо за внимание!