Комбинаторика многогранников

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

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

Грани и вектора подсчёта граней

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

Грань выпуклого многогранника P можно определить как пересечение P и замкнутого полупространства H, такого, что граница H не содержит внутренних точек P. Размерность грани равна размерности этого пересечения. 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₋₁ = 1 отражает пустое множество в качестве грани, в то время как f_d = 1 отражает сам P. Для куба расширенный ƒ-вектор — это (1,8,12,6,1), а для октаэдра — (1,6,12,8,1). Хотя вектора этих примеров унимодальны (элементы слева направо сначала возрастают, а затем убывают), существуют многогранники более высоких размерностей, для которых это неверно.

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

Равенства и неравенства

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

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

Ещё одно важное неравенство для числа граней многогранника получается из теоремы о верхней оценке, впервые доказанной МакМалленом, которая утверждает, что 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-связным планарным графом.

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

В контексте симплекс-метода линейного программирования важно учитывать диаметр многогранника, минимальное число вершин, которые необходимо пройти, чтобы достичь любую вершину из любой другой вершины. Система линейных неравенств задачи линейного программирования определяет грани многогранника допустимых решений задачи и симплекс-метод находит оптимальное решение, проходя путь по рёбрам этого многогранника. Таким образом, диаметр оценивает нижнюю границу числа шагов этого метода. Опровергнутая гипотеза Хирша давала сильную верхнюю оценку на диаметр. Известна более слабая (квазиполиномиальная) верхняя оценка диаметра, а гипотеза Хирша доказана для отдельных классов многогранников.

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

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

Грани 0-1 многогранников

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

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

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

См. также

• Абстрактный многогранник
• Абстрактная коммутативная алгебра
• Симплициальная сфера

Литература

• Michel L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11. — С. 431–434. — doi:10.2140/pjm.1961.11.431..
• Roswitha Blind, Peter Mani-Levitska. Puzzles and polytope isomorphisms // Aequationes Mathematicae. — 1987. — Т. 34, вып. 2-3. — С. 287–297. — doi:10.1007/BF01830678..
• William Cook, Paul D. Seymour. Polyhedral Combinatorics. — American Mathematical Society, 1989. — (DIMACS Series in Discrete Mathematics and Theoretical Computer Science). — ISBN 978-0-8218-6591-0..
• Eric J. Friedman. Finding a simple polytope from its graph in polynomial time // Discrete and Computational Geometry. — 2009. — Т. 41, вып. 2. — С. 249–256. — doi:10.1007/s00454-008-9121-7..
• Christoph Haase, Stefan Kiefer. The Complexity of the Kth Largest Subset Problem and Related Problems. — 2015.
• A census of flag-vectors of 4-polytopes. — 2000.. В Kalai, Ziegler, 2000, стр. 105—110.
• Gil Kalai. A simple way to tell a simple polytope from its graph // Journal of Combinatorial Theory. — 1988. — Т. 49, вып. 2. — С. 381–383. — doi:10.1016/0097-3165(88)90064-7..
• Gil Kalai, Daniel Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra // Bulletin of the American Mathematical Society. — 1992. — Т. 26, вып. 2. — С. 315–316. — doi:10.1090/S0273-0979-1992-00285-9. — arXiv:math/9204233..
• Gil Kalai, Günter M. Ziegler (2000), Polytopes: Combinatorics and Computation, vol. 29, Birkhäuser, ISBN 978-3-7643-6351-2 {{citation}}: Неизвестный параметр |серия= игнорируется (справка).
• Peter McMullen. The maximum numbers of faces of a convex polytope // Mathematika. — 1970. — Т. 17. — С. 179–184. — doi:10.1112/S0025579300002850..
• Denis Naddef. The Hirsch conjecture is true for (0,1)-polytopes // Mathematical Programming. — 1989. — Т. 45, вып. 1. — С. 109–110. — doi:10.1007/BF01589099..
• Francisco Santos. A counterexample to the Hirsch conjecture // Annals of Mathematics. — Princeton University and Institute for Advanced Study, 2012. — Т. 176, вып. 1. — С. 383–412. — doi:10.4007/annals.2012.176.1.7. — arXiv:1006.2814.
• Alexander Schrijver. Polyhedral Combinatorics. — Centrum voor Wiskunde en Informatica, 1987..
• Ernst Steinitz. Über die Eulerschen Polyederrelationen. — Archiv für Mathematik und Physik. — 1906. — Т. 11. — С. 86–88..
• Günter M. Ziegler. Lectures on Polytopes. — Springer-Verlag, 1995. — Т. 152. — (Graduate Texts in Mathematics). — ISBN 0-387-94365-X..
• Günter M. Ziegler. Lectures on 0-1 polytopes. — 2000.. В Kalai, Ziegler, 2000.

Ссылки

• Gil Kalai. Five Open Problems Regarding Convex Polytopes (англ.) // Combinatorics and more : сайт. — 2008. — 7 May.