Русская Википедия:Смежностный многогранник
k-Смежностный многогранник — это выпуклый многогранник, в котором любое k-элементное подмножество его вершин является множеством вершин некоторой грани этого многогранника.
Определения
Выпуклый многогранник, в котором любое k-элементное подмножество его вершин является множеством вершин некоторой грани этого многогранника, называется k-смежностнымШаблон:Sfn.
Простой многогранник называется двойственно смежностным, если любые k его гиперграней имеют непустое пресечение (которое в этом случае является гранью коразмерности k) Шаблон:Sfn.
Говорят, что многогранник смежностный без спецификации k, если он k-смежностный для <math>k=\lfloor d/2 \rfloor</math>. Если исключить симплексы, это будет максимально возможное значение для k. Фактически, любой многогранник, k-смежностный для некоторого <math>k\ge 1 + \lfloor d/2 \rfloor</math>, является симплексомШаблон:Sfn.
Примеры
- 2-смежностный многогранник — это многогранник, в котором каждая пара вершин связана ребром. Таким образом, граф 2-смежностного многогранника является полным графом. 2-смежностные многогранники с числом вершин более четырёх могут существовать только в пространствах размерности 4 и выше (и, в общем случае, k-смежностный многогранник, отличный от симплекса, требует размерности 2k и выше).
- Произведение <math>P=\Delta^2 \times \Delta^2</math> двух треугольников является простым многогранником и легко видеть, что любые две его гиперграни пересекаются по некоторой 2-грани. Таким образом, этот многогранник является двойственно 2-смежностным. Полярный многогранник <math>P^*</math> является смежностным симплициальным 4-многогранникомШаблон:Sfn.
- d-Симплекс является d- смежностным многогранником.
В k-смежностном многограннике с <math>k \geqslant 3</math>, любая 2-грань должна быть треугольной, а в k- смежностном многограннике с <math>k \geqslant 4</math> любая 3-грань должна быть тетраэдром. В общем случае в любом k-смежностном многограннике все грани размерности меньшей k являются симплексами.
Циклические многогранники
Циклические многогранники, образованные как выпуклые оболочки конечного числа точек кривой моментов (t, t2, ..., td) в d-мерном пространстве, автоматически являются смежностными многогранниками. (Из тождества для определителя Вандермонда вытекает, что никакие (d + 1) точек на кривой моментов не лежат на одной аффинной гиперплоскости. Таким образом, многогранник является симплициальным d-многогранникомШаблон:Sfn)
Теодор Моцкин высказал гипотезу, что все смежностные многогранники комбинаторно эквивалентны циклическим многогранникамШаблон:Sfn. Однако, вопреки этому, существует много смежностных многогранников, не являющихся циклическими — число комбинаторно различных смежностных многогранников растёт суперэкспоненциально как по числу вершин, так и по размерностиШаблон:Sfn.
Общие свойства
Выпуклая оболочка множества нормально распределённых случайных точек, когда число точек пропорционально размерности, с большой вероятностью является k-смежностным многогранником для k, которое также пропорционально размерностиШаблон:Sfn.
Число граней всех размерностей смежностного многогранника в пространствах чётной размерности определяется исключительно размерностью пространства и числа вершин уравнением Дена — Сомервиля — число k-мерных граней fk удовлетворяет неравенству
- <math>f_{k-1} \le \sum_{i=0}^{d/2} {}^* \left( \binom{d-i}{k-i}+\binom{i}{k-d+i} \right) \binom{n-d-1+i}{i},</math>
где звёздочка означает прекращение суммирования на <math>i=\lfloor d/2\rfloor</math> и конечный член суммы должен быть поделён на два, если d чётноШаблон:Sfn. Согласно Шаблон:Не переведено 5 МакмулленаШаблон:Sfn, смежностные многогранники достигают максимального числа граней среди n-вершинных d-мерных выпуклых многогранников.
Обобщённая версия задачи со счастливым концом применяется к набору точек в пространстве высокой размерности и подразумевает, что для любой размерности d и любого n > d существует число m(d,n) со свойством, что любые m точек в общем положении в d-мерном пространстве содержит подмножество из n точек, образующих вершины смежностного многогранникаШаблон:Sfn[1]
Гипотеза Максименко
Число вершин 2-смежностного многогранника не превосходит числа его фасет. Гипотеза справедлива для случаев d < 7 (малая размерность) и <math>f_0 < d + 6</math>(небольшое число вершин, f0 — число вершин)Шаблон:Sfn.
Примечания
Литература
- Шаблон:Публикация
- Шаблон:Citation
- Шаблон:Публикация
- Шаблон:Публикация
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- ↑ Грюнбаум приписывает основную лемму в этом результате, что любое множество d + 3 точек содержит вершины циклического многогранника с (d + 2) вершинами Мише Перлесу.
