Полиэдральная комбинаторика — раздел математики в рамках комбинаторики и дискретной геометрии , изучающий проблемы подсчёта и описания граней выпуклых многогранников и выпуклых многогранников более высокой размерности .
Исследования в области полиэдральной комбинаторики делятся на две отдельные области. Математики в этой области изучают комбинаторику многогранников; например, они ищут неравенства , которые описывают отношения между количеством вершин , ребер и граней более высоких измерений в произвольных многогранниках или в некоторых важных подклассах многогранников, а также изучают другие комбинаторные свойства многогранников, такие как их связность и диаметр (число многогранников). шаги, необходимые для достижения любой вершины из любой другой вершины). Кроме того, многие ученые-компьютерщики используют фразу «многогранная комбинаторика» для описания исследований по точным описаниям граней некоторых конкретных многогранников (особенно многогранников 0-1, вершины которых являются подмножествами гиперкуба ) , возникающих в результате задач целочисленного программирования .
Грань выпуклого многогранника P можно определить как пересечение P и замкнутого полупространства H такое, что граница H не содержит внутренних точек P . Размер лица — это размер этого корпуса. 0-мерные грани — это сами вершины, а 1-мерные грани (называемые ребрами ) — это отрезки прямых , соединяющие пары вершин. Обратите внимание, что это определение также включает в себя как грани пустое множество и весь многогранник P . Если сам P имеет размерность d , грани P с размерностью d −1 называются гранями P , а грани с размерностью d −2 называются гребнями . [1] Грани P могут быть частично упорядочены путем включения, образуя решетку граней , верхним элементом которой является сам P , а нижним элементом - пустое множество.
Ключевым инструментом в полиэдральной комбинаторике является ƒ-вектор многогранника, [2] вектор ( f 0 , f 1 , ..., f d − 1 ), где f i — количество i -мерных особенностей многогранника. . Например, куб имеет восемь вершин, двенадцать ребер и шесть граней, поэтому его ƒ-вектор равен (8,12,6). Двойственный многогранник имеет ƒ-вектор с теми же номерами в обратном порядке; так, например, правильный октаэдр , двойственный кубу, имеет ƒ-вектор (6,12,8). Матрицы конфигурации включают f-векторы правильных многогранников в качестве диагональных элементов.
Расширенный ƒ-вектор формируется путем объединения числа один на каждом конце ƒ-вектора и подсчета количества объектов на всех уровнях решетки граней; в левой части вектора f −1 = 1 считает пустое множество гранью, а в правой части f d = 1 считает сам P. Для куба расширенный ƒ-вектор равен (1,8,12,6,1), а для октаэдра — (1,6,12,8,1). Хотя векторы для этих примеров многогранников унимодальны (коэффициенты, взятые в порядке слева направо, увеличиваются до максимума, а затем уменьшаются), существуют многомерные многогранники, для которых это неверно. [3]
Для симплициальных многогранников (многогранников, в которых каждая грань является симплексом ) часто бывает удобно преобразовать эти векторы, создав другой вектор, называемый h -вектором. Если мы интерпретируем члены ƒ-вектора (опуская последнюю единицу) как коэффициенты полинома ƒ( x ) = Σ f i x d − i − 1 (например, для октаэдра это дает полином ƒ( x ) = x 3 + 6 x 2 + 12 x + 8), то h -вектор перечисляет коэффициенты многочлена h ( x ) = ƒ( x − 1) (опять же, для октаэдра h ( x ) = x 3 + 3 х 2 + 3 х + 1). [4] Как пишет Циглер, «для различных задач о симплициальных многогранниках h -векторы являются гораздо более удобным и кратким способом кодирования информации о номерах граней, чем ƒ-векторы».
Наиболее важным соотношением между коэффициентами ƒ-вектора многогранника является формула Эйлера Σ(−1) i 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 вершинами может иметь не более такого же количества граней любой другой размерности, как соседний многогранник с одинаковое количество вершин:
где звездочка означает, что последний член суммы должен быть уменьшен вдвое, когда d четно. [6] Асимптотически это означает, что существует не более граней всех измерений.
Даже в четырех измерениях набор возможных ƒ-векторов выпуклых многогранников не образует выпуклое подмножество четырехмерной целочисленной решетки, и многое остается неизвестным о возможных значениях этих векторов. [7]
Наряду с исследованием числа граней многогранников исследователи изучали и другие их комбинаторные свойства, такие как описания графов, полученных из вершин и ребер многогранников (их 1-скелета ).
Теорема Балинского утверждает, что граф, полученный таким образом из любого d -мерного выпуклого многогранника, является d -вершинно связным . [8] В случае трехмерных многогранников это свойство и планарность могут быть использованы для точной характеристики графиков многогранников: теорема Стейница утверждает, что G является скелетом трехмерного многогранника тогда и только тогда, когда G является 3-мерным многогранником. планарный граф с вершинной связностью. [9]
Теорема Блинда и Мани-Левитски (1987) (ранее высказанная Михой Перлесом ) утверждает, что можно восстановить структуру грани простого многогранника по его графику. То есть, если данный неориентированный граф является скелетом простого многогранника, существует только один многогранник (с точностью до комбинаторной эквивалентности), для которого это верно. Это резко контрастирует с (непростыми) соседними многогранниками, граф которых является полным графом ; в одном и том же графе может быть много разных соседних многогранников. Другое доказательство этой теоремы, основанное на уникальных ориентациях стоков, было дано Калаем (1988), а Фридман (2009) показал, как использовать эту теорему для получения алгоритма с полиномиальным временем для восстановления решеток граней простых многогранников по их графикам. Однако проверка того, может ли данный граф или решетка быть реализована как решетка граней простого многогранника, эквивалентна (по полярности) реализации симплициальных многогранников , которая была показана полной для экзистенциальной теории вещественных чисел Адипрасито и Падролом ( 2014) .
В контексте симплекс-метода линейного программирования важно понимать диаметр многогранника — минимальное количество ребер, необходимое для достижения любой вершины по пути из любой другой вершины. Система линейных неравенств линейной программы определяет грани многогранника, представляющие все возможные решения программы, а симплексный метод находит оптимальное решение, следуя по пути в этом многограннике. Таким образом, диаметр обеспечивает нижнюю границу количества шагов, необходимых для этого метода. Гипотеза Хирша , ныне опровергнутая, предполагает строгую (линейную) границу того, насколько большим может быть диаметр многогранника с фиксированным размером и количеством граней . [10] Известны более слабые (квазиполиномиальные по и ) верхние оценки их диаметра, [11] , а также доказательства гипотезы Хирша для специальных классов многогранников. [12]
Решение о том, ограничено ли количество вершин данного многогранника некоторым натуральным числом k, является вычислительно сложной задачей, полной для класса сложности PP . [13]
В контексте методов секущей плоскости целочисленного программирования важно иметь возможность точно описывать грани многогранников, вершины которых соответствуют решениям задач комбинаторной оптимизации. Часто эти проблемы имеют решения, которые могут быть описаны двоичными векторами , а соответствующие многогранники имеют координаты вершин, которые все равны нулю или единице.
В качестве примера рассмотрим многогранник Биркгофа — набор матриц размера n × n , которые можно сформировать из выпуклых комбинаций матриц перестановок . Эквивалентно, его вершины можно рассматривать как описание всех идеальных паросочетаний в полном двудольном графе , а задачу линейной оптимизации на этом многограннике можно интерпретировать как двудольную задачу идеального паросочетания с минимальным весом. Теорема Биркгофа – фон Неймана утверждает, что этот многогранник можно описать двумя типами линейного неравенства или равенства. Во-первых, для каждой ячейки матрицы существует ограничение на то, что эта ячейка имеет неотрицательное значение. Во-вторых, для каждой строки или столбца матрицы существует ограничение, согласно которому сумма ячеек в этой строке или столбце равна единице. Ограничения строки и столбца определяют линейное подпространство размерности n 2 - 2 n + 1, в котором лежит многогранник Биркгофа, а ограничения неотрицательности определяют грани многогранника Биркгофа внутри этого подпространства.
Однако многогранник Биркгофа необычен тем, что доступно полное описание его граней. Для многих других многогранников 0–1 существует экспоненциально или суперэкспоненциально много фасетов, и доступны только частичные описания их фасетов. [14]
