Суміжнісний багатогранник

Опуклий багатогранник, у якому будь-яка k-елементна підмножина вершин є множиною вершин деякої грані цього багатогранника, називається k-суміжнісним[1].

Простий багатогранник називається двоїсто суміжнісним, якщо будь-які k його гіперграней мають непорожній перетин (який у цьому випадку є гранню корозмірності k)[2].

Кажуть, що багатогранник суміжнісний без специфікації k, якщо він k-суміжнісний для ${\displaystyle k=\lfloor d/2\rfloor }$. Якщо виключити симплекси, це буде найбільше можливе значення для k. Фактично, будь-який багатогранник, k-суміжнісний для деякого ${\displaystyle k\geq 1+\lfloor d/2\rfloor }$, є симплексом[3].

• 2-суміжнісний багатогранник — це багатогранник, у якому кожна пара вершин пов'язана ребром. Таким чином, граф 2-суміжнісного багатогранника є повним графом. 2-суміжнісні багатогранники з числом вершин більш як чотири можуть існувати тільки в просторах розмірності 4 і вище (і, в загальному випадку, k-суміжнісний багатогранник, відмінний від симплекса, вимагає розмірності 2k і вище).
• Добуток ${\displaystyle P=\Delta ^{2}\times \Delta ^{2}}$ двох трикутників є простим багатогранником і легко бачити, що будь-які дві його гіперграні перетинаються по деякій 2-грані. Таким чином, цей багатогранник є двоїсто 2-суміжнісним. Полярний багатогранник ${\displaystyle P^{*}}$ є суміжнісним симпліціальним 4-багатогранником[2].
• d-симплекс є d-суміжнісним багатогранником.

В k-суміжнісному багатограннику з ${\displaystyle k\geqslant 3}$, будь-яка 2-грань повинна бути трикутною, а в k-суміжнісному багатограннику з ${\displaystyle k\geqslant 4}$ будь-яка 3-грань повинна бути тетраедром. У загальному випадку в будь-якому k-суміжнісному багатограннику всі грані з розмірністю менше від k є симплексами.

Циклічні багатогранники, утворені як опуклі оболонки скінченного числа точок кривої моментів (t, t², …, t^d) у d-вимірному просторі, автоматично є суміжнісними багатогранниками. (З тотожності для визначника Вандермонда випливає, що ніякі (d + 1) точок на кривій моментів не лежать на одній афінній гіперплощині. Таким чином, багатогранник є симпліціальним d-багатогранником[2])

Теодор Моцкін висловив гіпотезу, що всі суміжнісні багатогранники комбінаторно еквівалентні циклічним багатогранникам[4]. Однак, всупереч цьому, існує багато суміжнісних багатогранників, які не є циклічними — число комбінаторно різних суміжнісних багатогранників зростає суперекспоненційно як за числом вершин, так і за розмірністю[5].

Опукла оболонка множини нормально розподілених випадкових точок, коли число точок пропорційне розмірності, з великою вірогідністю є k-суміжнісним багатогранником для k, яке також пропорційне розмірності[6].

Число граней усіх розмірностей суміжнісного багатогранника в просторах парної розмірності визначається виключно розмірністю простору і числом вершин за рівнянням Дена — Сомервіля: число k-вимірних граней f_k задовольняє нерівності

${\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}},}$

де зірочка означає припинення підсумовування на ${\displaystyle i=\lfloor d/2\rfloor }$ і кінцевий член суми повинен бути поділений на два, якщо d парне[7]. Згідно з теоремою про верхню оцінку Макмуллена[8], суміжнісні багатогранники досягають найбільшого числа граней серед n-вершинних d-вимірних опуклих багатогранників.

Узагальнена версія задачі зі щасливим кінцем застосовується до набору точок у просторі високої розмірності і передбачає, що для будь-якої розмірності d і будь-якого n > d існує число m(d,n) із властивістю, що будь-які m точок у загальному положенні в d-вимірному просторі містять підмножину з n точок, що утворюють вершини суміжнісного багатогранника[9][10]

Число вершин 2-суміжнісного багатогранника не перевищує числа його фасет. Гіпотеза справедлива для випадків d < 7 (мала розмірність) і ${\displaystyle f_{0}<d+6}$ (невелике число вершин, f₀ — число вершин)[1].