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

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

Грань опуклого многогранника 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] .

Ще одна важлива нерівність для числа граней многогранника виходить з теореми про верхню оцінку^[en], вперше доведеної МакМалленом^[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-кістяка).

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

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

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

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

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

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

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

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

• 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.