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

Комбінато́рика многогра́нників — це галузь математики, що належить до комбінаторики і комбінаторної геометрії і вивчає питання підрахунку й опису граней опуклих многогранників.

Дослідження в комбінаториці многогранників розпадаються на дві гілки. Математики, які працюють у цій галузі, вивчають комбінаторику многогранників; наприклад, вони шукають нерівності, які описують відносини між числом вершин, ребер і граней різних розмірностей у довільному многограннику, а також вивчають інші комбінаторні властивості многогранників, такі як зв'язність і діаметр (число кроків, необхідних для досягнення будь-якої вершини з будь-якої іншої вершини). Крім того, багато вчених, що працюють у галузі інформатики, використовують фразу «комбінаторика многогранників» для опису досліджень з точного опису граней певних многогранників (особливо, 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) як коефіцієнти многочлена f(x) = Σf_ix^{d − i − 1} (наприклад, для октаедра це дає многочлен f(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 ≤ 3 v — 6 і f ≤ 2 v — 4. З огляду на двоїстість e ≤ 3 f — 6 і v ≤ 2 f — 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-зв'язним планарним графом.

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

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

Обчислювальні властивості

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

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

Важливо в контексті методів відсікань цілочисельного програмування мати можливість описати точно фасети (грані) многогранника, на яких лежать вершини, відповідні розв'язкам комбінаторних оптимізаційних задач. Часто такі завдання мають розв'язки, які можна задати бітовими векторами, а відповідні многогранники мають вершини, координатами яких є числа 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. — (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. — С. 315–316. — arXiv:math/9204233. — DOI:10.1090/S0273-0979-1992-00285-9..
• , ISBN 978-3-7643-6351-2 {{citation}}: Пропущений або порожній |title= (довідка).
• 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. — 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.. В Kalai, Ziegler, 2000.

Посилання

• Gil Kalai. Five Open Problems Regarding Convex Polytopes // Combinatorics and more : сайт. — 2008. — . — 5. Архівовано з джерела 14 Серпня 2020. Процитовано 14 Листопада 2020.