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