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

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

Визначення

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

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

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

Приклади

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

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

Циклічні многогранники

Докладніше: Циклічний многогранник

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

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

Загальні властивості

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

Число граней усіх розмірностей суміжнісного многогранника в просторах парної розмірності визначається виключно розмірністю простору і числом вершин за рівнянням Дена — Сомервіля: число 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 парне. Згідно з ^[en] Макмуллена, суміжнісні многогранники досягають найбільшого числа граней серед n-вершинних d-вимірних опуклих многогранників.

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

Гіпотеза Максименко

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

Примітки

1. Максименко, 2010.
2. Панов, 2009.
3. Grünbaum, 2003, с. 123.
4. Gale, 1963, с. 225–233.
5. Shemer, 1982, с. 291–314.
6. Donoho, Tanner, 2005, с. 9452–9457.
7. Ziegler, 1995, с. 254–258.
8. McMullen, 1970, с. 179–184.
9. Grünbaum, 2003, с. 126.
10. Ґрюнбаум приписує основну лему в цьому результаті, що будь-яка множина з d + 3 точок містить вершини циклічного многогранника з (d + 2) вершинами ^[en].

Література

• Максименко, А.Н. О числе фасет 2-смежностного многогранника. — Модел. И анализ информ. Систем. — 2010. — № 1. — С. 76-82.
• Grünbaum Branko. Convex Polytopes / Volker Kaibel, Victor Klee, Günter M. Ziegler. — , 2003. — Т. 221. — С. 123. — (Graduate Texts in Mathematics) — .
• Панов Т.Е. Топология и комбинаторика действий торов. — Москва : Московский государственный университет имени М. В. Ломоносова, 2009. — С. 23. — (Диссертация на соискание учёной степени доктора физико-математических наук).
• David Gale. Convexity, Seattle, 1961 / Victor Klee. — American Mathematical Society, 1963. — С. 225–233. — (Symposia in Pure Mathematics). — .
• Ido Shemer. Neighborly polytopes // Israel Journal of Mathematics. — 1982. — Т. 43, вип. 4 (25 липня). — С. 291–314. — DOI:10.1007/BF02761235.
• David L. Donoho, Jared Tanner. Neighborliness of randomly projected simplices in high dimensions // Proceedings of the National Academy of Sciences of the United States of America. — 2005. — Т. 102, вип. 27 (25 липня). — С. 9452–9457. — DOI:10.1073/pnas.0502258102. — PMID 15972808 .
• Günter M. Ziegler. Lectures on Polytopes. — , 1995. — Т. 152. — С. 254–258. — (Graduate Texts in Mathematics) — .
• Peter McMullen. The maximum numbers of faces of a convex polytope // Mathematika. — 1970. — Т. 17 (25 липня). — С. 179–184. — DOI:10.1112/S0025579300002850.
• Branko Grünbaum. Convex Polytopes / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2nd. — , 2003. — Т. 221. — С. 126. — (Graduate Texts in Mathematics) — .