PROFILPELAJAR.COM

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

Визначення

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

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

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

Приклади

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

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

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

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

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

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

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

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

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

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}},

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

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

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

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

Примітки

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

Література

Максименко, А.Н. О числе фасет 2-смежностного многогранника. — Модел. И анализ информ. Систем. — 2010. — № 1. — С. 76-82.
Grünbaum Branko. Convex Polytopes / Volker Kaibel, Victor Klee, Günter M. Ziegler. — Springer-Verlag, 2003. — Т. 221. — С. 123. — (Graduate Texts in Mathematics) — ISBN 0-387-00424-6.
Панов Т.Е. Топология и комбинаторика действий торов. — Москва : Московский государственный университет имени М. В. Ломоносова, 2009. — С. 23. — (Диссертация на соискание учёной степени доктора физико-математических наук).
David Gale. Convexity, Seattle, 1961 / Victor Klee. — American Mathematical Society, 1963. — С. 225–233. — (Symposia in Pure Mathematics). — ISBN 978-0-8218-1407-9.
Ido Shemer. Neighborly polytopes // Israel Journal of Mathematics. — 1982. — Т. 43, вип. 4 (15 січня). — С. 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 (15 січня). — С. 9452–9457. — DOI:10.1073/pnas.0502258102. — PMID 15972808 .
Günter M. Ziegler. Lectures on Polytopes. — Springer-Verlag, 1995. — Т. 152. — С. 254–258. — (Graduate Texts in Mathematics) — ISBN 0-387-94365-X.
Peter McMullen. The maximum numbers of faces of a convex polytope // Mathematika. — 1970. — Т. 17 (15 січня). — С. 179–184. — DOI:10.1112/S0025579300002850.
Branko Grünbaum. Convex Polytopes / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2nd. — Springer-Verlag, 2003. — Т. 221. — С. 126. — (Graduate Texts in Mathematics) — ISBN 0-387-00424-6.