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

Ґратка граней опуклого багатогранника.

Грань опуклого багатогранника P можна визначити як перетин P і замкнутого півпростору H, такого, що межа H не містить внутрішніх точок P. Розмірність грані дорівнює розмірності цього перетину. 0-вимірні грані — це самі вершини, а 1-вимірні грані (їх називають ребрами) є відрізками, що з'єднують пари вершин. Зауважимо, що це визначення включає як грані порожні множини і весь багатогранник P. Якщо P має розмірність d, грані P з розмірністю d − 1 називають фасетами багатогранника P, а межі розмірності d − 2 називають гребенями[1]. Межі P можуть бути частково впорядкованими за включенням, утворюючи ґратку граней, що має на вершині сам багатогранник P і порожню множину внизу.

Ключовим методом комбінаторики багатогранників є розгляд ƒ-вектора багатогранника[2] — вектора (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). Хоча вектори цих прикладів унімодальні (зліва направо спочатку зростають, а потім зменшуються), існують багатогранники більш високих розмірностей, для яких це не так[3].

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

Найважливіше співвідношення коефіцієнтів ƒ-вектора багатогранника — це формула Ейлера Σ(-1)ⁱf_i = 0, де підсумовування ведеться за елементами розширеного ƒ-вектора. У тривимірному просторі перенесення двох одиниць з лівого і правого боку розширеного ƒ-вектора (1, v, e, f, 1) в праву частину рівності перетворює рівність до більш звичного вигляду v - e + f = 2. З того факту, що будь-яка грань тривимірного багатогранника має щонайменше три ребра, слідує, що 2e ≥ 3f. Використовуючи цей вираз для виключення 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] .

Ще одна важлива нерівність для числа граней багатогранника виходить з теореми про верхню оцінку , вперше доведеної МакМалленом[6], яка стверджує, що d-вимірний багатогранник з n вершинами може мати не більше граней будь-якої розмірності, ніж суміжнісний багатогранник з таким самим числом вершин:

${\displaystyle 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 парне[7]. В асимптоті з цього випливає, що не може бути більше ніж ${\displaystyle \scriptstyle O(n^{\lfloor d/2\rfloor })}$ граней усіх розмірностей.

Навіть для розмірності чотири множина всіх можливих ƒ-векторів опуклих багатогранників не утворює опуклої підмножини чотиривимірної цілочисельної ґратки та багато залишається неясним про можливі значеннях цих векторів[8].

Поряд з числом граней багатогранників дослідники вивчають й інші їхні комбінаторні властивості, такі як властивості графів, одержуваних з вершин і ребер багатогранників (їх 1-кістяка).

Теорема Балінського стверджує, що граф, отриманий таким шляхом з будь-якого d-вимірного опуклого багатогранника, є вершинно d-зв'язним[9][10]. У разі тривимірних багатогранників цю властивість і планарність можна використати для точного опису графів багатогранників — теорема Штайніца стверджує, що G є кістяком тривимірного багатогранника тоді і тільки тоді, коли G є вершинно 3-зв'язним планарним графом[11].

Теорема Блайнда і Мані-Левицької[12] (сформульована як гіпотеза Міхою Перле) стверджує, що можна відновити структуру граней простого багатогранника за його графом. Тобто, якщо даний неорієнтований граф є кістяком простого багатогранника, є тільки один багатогранник (з точністю до комбінаторної еквівалентності), для якого граф є кістяком. Ця властивість різко контрастує з властивостями суміжнісних (не простих) багатогранників, графи яких є повними — може існувати багато різних суміжнісних багатогранників з одним і тим самим графом. Інше доведення цієї теореми дав Калаї[13], а Фрідман[14] показав, як використовувати цю теорему для створення алгоритму з поліноміальних часом для побудови простих багатогранників за їхніми графам.

В контексті симплекс-методу лінійного програмування важливо враховувати діаметр багатогранника, мінімальне число вершин, які необхідно пройти, щоб досягти будь-якої вершини з будь-якої іншої вершини. Система лінійних нерівностей задачі лінійного програмування визначає межі багатогранника допустимих розв'язків задачі і симплекс-метод знаходить оптимальний розв'язок, проходячи шлях по ребрах цього багатогранника. Таким чином, діаметр оцінює нижню межу числа кроків цього методу. Спростована гіпотеза Гірша давала сильну верхню оцінку на діаметр[15]. Відома слабша (квазіполіноміальна) верхня оцінка діаметра[16], а гіпотезу Гірша доведено для окремих класів багатогранників[17].

Визначення того, чи обмежене число вершин заданого багатогранника деяким натуральним числом k, є складною задачею і належить класу складності PP[18].

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

Як приклад візьмемо багатогранник Біркгофа, множину n × n матриць, які можна утворити опуклими комбінаціями матриць перестановок. Також, вершини цього багатогранника можна розуміти як опис усіх виконаних парувань повного дводольного графу, а задачу лінійної оптимізації на цьому багатограннику можна розглядати як задачу пошуку зваженого мінімального виконаного парування. Теорема Біркгофа стверджує, що такий багатогранник можна описати за допомогою двох типів лінійних нерівностей. По-перше, кожен елемент матриці невід'ємний, по-друге, для кожного стовпця і для кожного рядка сума елементів матриці дорівнює одиниці. Обмеження на суму по рядках і стовпцях визначають лінійний підпростір розмірності n² − 2n + 1, в якому лежить багатогранник Біркгофа, а обмеження на невід'ємність елементів матриці задають грані багатогранника в цьому підпросторі.

Багатогранник Біркгофа незвичайний тим, що відомий повний опис його граней. Для багатьох інших 0-1 багатогранників існує експоненційно (або суперекспоненційно) багато граней і доступний тільки частковий їх опис[19].

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

• Michel L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11 (17 лютого). — С. 431–434. — DOI:10.2140/pjm.1961.11.431..
• Roswitha Blind, Peter Mani-Levitska. Puzzles and polytope isomorphisms // Aequationes Mathematicae. — 1987. — Т. 34, вип. 2-3 (17 лютого). — С. 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 (17 лютого). — С. 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. — 17 лютого.
• A census of flag-vectors of 4-polytopes. — 2000. — 17 лютого.. В 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 (17 лютого). — С. 381–383. — (Series A). — 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 (17 лютого). — С. 315–316. — arXiv:math/9204233. — DOI:10.1090/S0273-0979-1992-00285-9..
• . ISBN 978-3-7643-6351-2. Пропущений або порожній |title= (довідка).
• Peter McMullen. The maximum numbers of faces of a convex polytope // Mathematika. — 1970. — Т. 17 (17 лютого). — С. 179–184. — DOI:10.1112/S0025579300002850..
• Denis Naddef. The Hirsch conjecture is true for (0,1)-polytopes // Mathematical Programming. — 1989. — Т. 45, вип. 1 (17 лютого). — С. 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 (17 лютого). — С. 383–412. — arXiv:1006.2814. — DOI:10.4007/annals.2012.176.1.7.
• 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. — 17 лютого.. В Kalai, Ziegler, 2000.

• Gil Kalai. Five Open Problems Regarding Convex Polytopes // Combinatorics and more : сайт. — 2008. — 5.