Полиэдральная комбинаторика

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

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

лиц

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

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

Ключевым инструментом полиэдральной комбинаторики является ƒ-вектор многогранника. вектор ( 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). Хотя векторы для этих примеров многогранников унимодальны (коэффициенты, взятые в порядке слева направо, увеличиваются до максимума, а затем уменьшаются), существуют многомерные многогранники, для которых это не так.

Для симплициальных многогранников (многогранников, в которых каждая грань является симплексом ) часто бывает удобно преобразовать эти векторы, создав другой вектор, называемый h -вектором. Если мы интерпретируем члены ƒ-вектора (опуская последнюю единицу) как коэффициенты многочлена ƒ( x ) = Σ f _i x ^{д - я - 1} (например, для октаэдра это дает полином ƒ( x ) = x ³ + 6x ² + 12 x + 8), то h -вектор перечисляет коэффициенты многочлена h ( x ) = ƒ( x − 1) (опять же, для октаэдра h ( x ) = x ³ + 3x ² + 3 х + 1). Как пишет Циглер, «для различных задач о симплициальных многогранниках 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. Из теоремы Стейница , что любой трехмерный целочисленный вектор, удовлетворяющий этим равенствам и неравенствам — ƒ-вектор выпуклого многогранника.

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

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

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

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

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

Теоретико-графовые свойства

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

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

Теорема Блинда и Мани-Левитски (1987) (ранее высказанная Михой Перлесом ) утверждает, что можно восстановить структуру грани простого многогранника по его графику. То есть, если данный неориентированный граф является скелетом простого многогранника, существует только один многогранник (с точностью до комбинаторной эквивалентности), для которого это верно. Это резко контрастирует с (непростыми) соседними многогранниками, граф которых является полным графом ; в одном и том же графе может быть много разных соседних многогранников. Другое доказательство этой теоремы, основанное на уникальных ориентациях стоков, было дано Калаем (1988) , а Фридман (2009) показал, как использовать эту теорему для получения алгоритма с полиномиальным временем для восстановления решеток граней простых многогранников по их графикам. Однако проверка того, может ли данный граф или решетка быть реализована как решетка граней простого многогранника, эквивалентна (по полярности) реализации симплициальных многогранников , которая, как было показано, является полной для экзистенциальной теории вещественных чисел. Адипрасито и Падрол (2017) .

В контексте симплекс-метода важно линейного программирования понимать диаметр многогранника — минимальное количество ребер, необходимое для достижения любой вершины по пути из любой другой вершины. Система линейных неравенств линейной программы определяет грани многогранника, представляющие все возможные решения программы, а симплексный метод находит оптимальное решение, следуя по пути в этом многограннике. Таким образом, диаметр обеспечивает нижнюю границу количества шагов, необходимых для этого метода. Гипотеза Хирша , ныне опровергнутая, предполагает сильную (линейную) оценку того, насколько велик диаметр многогранника с фиксированной размерностью. $d$ и количество граней $n$ может быть. Более слабый (квазиполиномиальный по $d$ и $n$) известны верхние границы их диаметра, а также доказательства гипотезы Хирша для специальных классов многогранников.

Вычислительные свойства

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

Фасеты многогранников 0-1

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

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

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

См. также

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

Ссылки

• Адипрасито, Карим А .; Падрол, Арнау (2017), «Теорема универсальности для соседних многогранников», Combinatorica , 37 (2): 129–136, arXiv : 1402.7207 , Bibcode : 2014arXiv1402.7207A , doi : 10.1007/s00493-016-3253-9 .
• Балинский, Мишель Л. (1961), «О графовой структуре выпуклых многогранников в n-пространстве», Pacific Journal of Mathematics , 11 (2): 431–434, doi : 10.2140/pjm.1961.11.431 .
• Слепой, Розвита ; Мани-Левитска, Питер (1987), «Загадки и изоморфизмы многогранников», Mathematical Equations , 34 (2–3): 287–297, doi : 10.1007/BF01830678 , MR   0921106 .
• Кук, Уильям; Сеймур, Пол Д. (1989), Полиэдральная комбинаторика , серия DIMACS по дискретной математике и теоретической информатике, Американское математическое общество , ISBN  978-0-8218-6591-0 .
• Фридман, Эрик Дж. (2009), «Нахождение простого многогранника по его графику за полиномиальное время», Discrete & Computational Geometry , 41 (2): 249–256, doi : 10.1007/s00454-008-9121-7 , MR   2471873 .
• Хаазе, Кристоф; Кифер, Стефан (2016), «Сложность проблемы K -го наибольшего подмножества и связанные с ней проблемы», Information Processing Letters , 116 (2): 111–115, arXiv : 1501.06729 , doi : 10.1016/j.ipl.2015.09.015 , S2CID   9195513
• Хеппнер, Андреа; Циглер, Гюнтер М. (2000), «Перепись векторов флагов 4-многогранников», в Калаи, Гил ; Циглер, Гюнтер М. (ред.), Многогранники — комбинаторика и вычисления , Семинар DMV, том. 29, стр. 105–110, номер документа : 10.1007/978-3-0348-8438-9_4 , ISBN.  978-3-7643-6351-2 .
• Калаи, Гил (1988), «Простой способ отличить простой многогранник по его графику», Журнал комбинаторной теории , серия A, 49 (2): 381–383, doi : 10.1016/0097-3165(88)90064- 7 , МР   0964396 .
• Калай, Гил ; Клейтман, Дэниел Дж. (1992), «Квазимолиномиальная оценка диаметра графов многогранников», Бюллетень Американского математического общества , 26 (2): 315–316, arXiv : math/9204233 , doi : 10.1090/ С0273-0979-1992-00285-9 , МР   1130448 .
• Калай, Гил ; Циглер, Гюнтер М. , ред. (2000), Многогранники — комбинаторика и вычисления , Семинар DMV, том. 29, Биркхойзер, номер номера : 10.1007/978-3-0348-8438-9 , ISBN  978-3-7643-6351-2 .
• МакМаллен, Питер (1970), «Максимальное количество граней выпуклого многогранника», Mathematika , 17 (2): 179–184, doi : 10.1112/S0025579300002850 .
• Наддеф, Денис (1989), «Гипотеза Хирша верна для (0,1)-многогранников», Mathematical Programming , 45 (1): 109–110, doi : 10.1007/BF01589099 , MR   1017214 .
• Сантос, Франциско (2012), «Контрпример к гипотезе Хирша», Annals of Mathematics , 176 (1), Принстонский университет и Институт перспективных исследований: 383–412, arXiv : 1006.2814 , doi : 10.4007/annals.2012.176.1.7 , МР   2925387
• Шрийвер, Александр (1987), Многогранная комбинаторика , Центр математики и информатики .
• Стейниц, Эрнст (1906), «О многогранных отношениях Эйлера», Архив математики и физики , 11 : 86–88 .
• Циглер, Гюнтер М. (1995), Лекции по многогранникам , Тексты для аспирантов по математике, том. 152, Springer-Verlag, номер домена : 10.1007/978-1-4613-8431-1 , ISBN.  0-387-94365-Х .
• Циглер, Гюнтер М. (2000), «Лекции о многогранниках 0-1», в Калаи, Гил ; Циглер, Гюнтер М. (ред.), Многогранники — комбинаторика и вычисления , Семинар DMV, том. 29, стр. 1–41, номер документа : 10.1007/978-3-0348-8438-9_1 , ISBN.  978-3-7643-6351-2 .

Внешние ссылки

• Калаи, Гил (2008), Пять открытых проблем, касающихся выпуклых многогранников .