Многогранная комбинаторика

Полиэдральная комбинаторика является филиалом математики , в пределах комбинаторики и дискретной геометрии , что исследования проблемы подсчета и описание граней выпуклых многогранников и многомерных выпуклые многогранников .

Исследования в области полиэдральной комбинаторики делятся на две отдельные области. Математики в этой области изучают комбинаторику многогранников; например, они ищут неравенства, которые описывают отношения между числами вершин , ребер и граней более высоких измерений в произвольных многогранниках или в некоторых важных подклассах многогранников, а также изучают другие комбинаторные свойства многогранников, такие как их связность и диаметр.(количество шагов, необходимых для достижения любой вершины из любой другой вершины). Кроме того, многие компьютерные ученые используют фразу «полиэдральная комбинаторика» для описания исследований точных описаний граней определенных конкретных многогранников (особенно многогранников 0-1, вершины которых являются подмножествами гиперкуба ), возникающих в результате задач целочисленного программирования .

Лица и векторы подсчета лиц [ править ]

Лицо решетки выпуклого многогранника.

Лицо выпуклого многогранника P может быть определенно как пересечение Р и закрытым полупространством Н таким образом, что граница Н не содержит внутреннюю точки P . Размер грани - это размер корпуса. 0-мерные грани - это сами вершины, а одномерные грани (называемые ребрами ) - это отрезки прямых, соединяющие пары вершин. Обратите внимание , что это определение включает в себя в качестве лица пустого множества , и всего многогранник P . Если сама P имеет размерность d , грани P с размерностью d - 1 называются гранями из P и грани с размерностью г  - 2 называются гребни . ^[1] Грани P могут быть частично упорядочены включением, образуя решетку граней, которая имеет в качестве верхнего элемента P сам, а в качестве нижнего элемента - пустое множество.

Ключевым инструментом в полиэдральной комбинаторике является ƒ-вектор многогранника, ^[2] вектор ( f ₀ , f ₁ , ..., f _{d  - 1} ), где f _i - количество i -мерных характеристик многогранника. . Например, куб имеет восемь вершин, двенадцать ребер и шесть граней, поэтому его ƒ-вектор равен (8,12,6). Двойной многогранник имеет ƒ-вектор с теми же номерами в обратном порядке; так, например, правильный октаэдр , двойственный кубу, имеет ƒ-вектор (6,12,8). Конфигурация матрицы включают f-векторы правильных многогранников как диагональные элементы.

Расширенная ƒ-вектор формируется путем конкатенации номера по одному на каждый конце ƒ-вектор, подсчет числа объектов на всех уровнях решетки лица; в левой части вектора f ₋₁  = 1 считает пустое множество как грань, а в правой части f _d  = 1 считает сам P. Для куба расширенный ƒ-вектор равен (1,8,12,6,1), а для октаэдра - (1,6,12,8,1). Хотя векторы для этого примера многогранников являются унимодальными (коэффициенты, взятые в порядке слева направо, увеличиваются до максимума, а затем уменьшаются), существуют многогранники более высокой размерности, для которых это неверно. ^[3]

Для симплициальных многогранников (многогранников, в которых каждая грань является симплексом ) часто бывает удобно преобразовать эти векторы, создав другой вектор, называемый h -вектором. Если мы интерпретируем члены ƒ-вектора (опуская последнюю 1) как коэффициенты многочлена ƒ ( x ) = Σ f _i x ^{d  -  i  - 1} (например, для октаэдра это дает многочлен ( x ) =  x ³  + 6 x ²  + 12 x  + 8), то h -вектор перечисляет коэффициенты многочлена h ( x) = ƒ ( x  - 1) (опять же, для октаэдра h ( x ) =  x ³  + 3 x ²  + 3 x  + 1). ^[4] Как пишет Зиглер, «для различных задач о симплициальных многогранниках h- векторы являются гораздо более удобным и кратким способом кодирования информации о числах граней, чем ƒ-векторы».

Равенство и неравенство [ править ]

Наиболее важным соотношением между коэффициентами ƒ-вектора многогранника является формула Эйлера Σ (−1) ⁱ f _i = 0, где члены суммы пробегают коэффициенты расширенного-вектора. В трех измерениях перемещение двух единиц на левом и правом концах расширенного ƒ-вектора (1, v , e , f , 1) в правую часть уравнения преобразует это тождество в более знакомую форму v - e + f = 2. Из того факта, что каждая грань трехмерного многогранника имеет не менее трех ребер, двойным подсчетом следует, что 2 e ≥ 3 f, и использование этого неравенства для исключения e и f из формулы Эйлера приводит к следующим неравенствам e ≤ 3 v - 6 и f ≤ 2 v - 4. По двойственности e ≤ 3 f - 6 и v ≤ 2 f - 4. Это Из теоремы Стейница следует, что любой трехмерный целочисленный вектор, удовлетворяющий этим равенствам и неравенствам, является ƒ-вектором выпуклого многогранника. ^[5]

В более высоких измерениях важны и другие соотношения между числами граней многогранника, в том числе уравнения Дена – Соммервилля, которые, выраженные через h- векторы симплициальных многогранников, принимают простую форму h _k = h _{d - k} для все к . Пример этих уравнений с k = 0 эквивалентен формуле Эйлера, но для d > 3 другие экземпляры этих уравнений линейно независимы друг от друга и ограничивают h -векторы (и, следовательно, также ƒ-векторы) дополнительными способами. ^[4]

Другое важное неравенство относительно количества граней многогранников дается теоремой о верхней оценке , впервые доказанной МакМалленом (1970) , которая утверждает, что d -мерный многогранник с n вершинами может иметь не более чем столько же граней любой другой размерности, сколько соседний многогранник с такое же количество вершин:

${\ displaystyle f_ {k-1} \ leq \ sum _ {i = 0} ^ {d / 2} {} ^ {*} \ left ({\ binom {di} {ki}} + {\ binom {i } {k-d + i}} \ right) {\ binom {nd-1 + i} {i}},}$

где звездочка означает, что последний член суммы должен быть уменьшен вдвое, когда d четно. ^[6] Асимптотически это означает, что существует не более граней всех размеров.${\ Displaystyle \ scriptstyle O (п ^ {\ lfloor d / 2 \ rfloor})}$

Даже в четырех измерениях набор возможных ƒ-векторов выпуклых многогранников не образует выпуклое подмножество четырехмерной целочисленной решетки, и многое остается неизвестным о возможных значениях этих векторов. ^[7]

Теоретико-графические свойства [ править ]

Наряду с исследованием количества граней многогранников, исследователи изучали другие их комбинаторные свойства, такие как описания графов, полученных из вершин и ребер многогранников (их 1-скелет ).

Теорема Балинского утверждает, что полученный таким образом граф из любого d -мерного выпуклого многогранника является d- вершинно-связным . ^[8] В случае трехмерных многогранников это свойство и планарность могут быть использованы для точной характеристики графов многогранников: теорема Стейница утверждает, что G является каркасом трехмерного многогранника тогда и только тогда, когда G является трехмерным. вершинно-связный планарный граф. ^[9]

Теорема Blind & Mani-Levitska (1987) (ранее выдвинутая Мишей Перлес ) утверждает, что можно восстановить структуру граней простого многогранника по его графику. То есть, если данный неориентированный граф является каркасом простого многогранника, существует только один многогранник (с точностью до комбинаторной эквивалентности), для которого это верно. Это резко контрастирует с (непростыми) соседними многогранниками, граф которых является полным графом ; для одного и того же графа может быть много разных соседних многогранников. Другое доказательство этой теоремы, основанное на уникальной ориентации стоков, было дано Калаи (1988) , а Фридман (2009) показал, как использовать эту теорему для выводаалгоритм с полиномиальным временем восстановления решеток граней простых многогранников по их графам. Тем не менее, тестирование ли данный граф или решетка может быть реализована в виде лицевой решетки простого многогранника эквивалентно (по полярности) к реализации симплициальных многогранников , который был показан , чтобы быть полными для экзистенциальной теории вещественных чисел по Adiprasito & Padrol ( 2014) .

В контексте симплекс - метода для линейного программирования , важно понимать диаметр многогранника, минимальное число ребер , необходимых для достижения любой вершины на пути из любой другой вершины. Система линейных неравенств линейной программы определяет фасеты многогранника, представляющего все возможные решения программы, а симплекс-метод находит оптимальное решение, следуя пути в этом многограннике. Таким образом, диаметр обеспечивает нижнюю границу количества шагов, необходимых для этого метода. Гипотеза Хирша , теперь опровергнутая, предполагала строгую оценку того, насколько большим может быть диаметр. ^[10]Известны более слабые (квазиполиномиальные) оценки диаметра сверху ^[11], а также доказательства гипотезы Хирша для специальных классов многогранников. ^[12]

Вычислительные свойства [ править ]

Определение того, ограничено ли количество вершин данного многогранника некоторым натуральным числом k, является сложной с вычислительной точки зрения задачей для класса сложности PP . ^[13]

Грани многогранников 0-1 [ править ]

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

В качестве примера, рассмотрим многогранник Биркгофа , множество п  ×  п матриц , которые могут быть образованы из выпуклых комбинаций из матриц перестановок . Эквивалентно, его вершины можно рассматривать как описывающие все совершенные паросочетания в полном двудольном графе , а задачу линейной оптимизации на этом многограннике можно интерпретировать как задачу о двудольном идеальном паросочетании с минимальным весом. Теорема Биркгофа – фон Неймана.утверждает, что этот многогранник может быть описан двумя типами линейного неравенства или равенства. Во-первых, для каждой ячейки матрицы существует ограничение, что эта ячейка имеет неотрицательное значение. Во-вторых, для каждой строки или столбца матрицы существует ограничение, согласно которому сумма ячеек в этой строке или столбце равна единице. Ограничения строки и столбца определяют линейное подпространство размерности n ²  - 2 n  + 1, в котором лежит многогранник Биркгофа, а ограничения неотрицательности определяют фасеты многогранника Биркгофа внутри этого подпространства.

Однако многогранник Биркгофа необычен тем, что доступно полное описание его граней. Для многих других многогранников 0-1 существует экспоненциально много или сверхэкспоненциально много граней, и доступны только частичные описания их граней. ^[14]

См. Также [ править ]

• Абстрактный многогранник
• Комбинаторная коммутативная алгебра
• Матроидный многогранник
• Многогранник порядка
• Симплициальная сфера
• Устойчивый согласующий многогранник

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

• Калаи, Гил (2008), Пять открытых задач о выпуклых многогранниках.