Смежностный многогранник

k-Смежностный многогранник — это выпуклый многогранник, в котором любое k-элементное подмножество его вершин является множеством вершин некоторой грани этого многогранника.

Определения

Выпуклый многогранник, в котором любое 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^2, ..., 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].

Примечания

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) вершинами Мише Перлесу.

Литература

• Максименко, А.Н. О числе фасет 2-смежностного многогранника // Модел. И анализ информ. Систем. — 2010. — Т. 17, № 1. — С. 76-82.
• Grünbaum Branko (2003), Convex Polytopes, vol. 221 (2nd ed.), Springer-Verlag, p. 123, ISBN 0-387-00424-6 {{citation}}: Неизвестный параметр |серия= игнорируется (справка)
• Панов Т.Е. Топология и комбинаторика действий торов. — Москва : Московский государственный университет имени М. В. Ломоносова, 2009. — С. 23. — (Диссертация на соискание учёной степени доктора физико-математических наук).
• David Gale. Convexity, Seattle, 1961 / Victor Klee. — American Mathematical Society, 1963. — Т. 7. — С. 225–233. — (Symposia in Pure Mathematics). — ISBN 978-0-8218-1407-9.
• Ido Shemer. Neighborly polytopes // Israel Journal of Mathematics. — 1982. — Т. 43, вып. 4. — С. 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. — С. 9452–9457. — doi:10.1073/pnas.0502258102. — PMID 15972808. — PMC 1172250.
• 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. — С. 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.