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

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

ОпределенияПравить

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

Простой многогранник называется двойственно смежностным, если любые k его гиперграней имеют непустое пресечение (которое в этом случае является гранью коразмерности k) .

Говорят, что многогранник смежностный без спецификации k, если он k-смежностный для $k=\lfloor <!--\; \lfloor \; -->d/2\rfloor <!--\; \rfloor \; -->$$k=\lfloor d/2\rfloor$ . Если исключить симплексы, это будет максимально возможное значение для k. Фактически, любой многогранник, k-смежностный для некоторого $k\ge <!--\; \ge \; -->1+\lfloor <!--\; \lfloor \; -->d/2\rfloor <!--\; \rfloor \; -->$$k\geq 1+\lfloor d/2\rfloor$ , является симплексом.

ПримерыПравить

2-смежностный многогранник — это многогранник, в котором каждая пара вершин связана ребром. Таким образом, граф 2-смежностного многогранника является полным графом. 2-смежностные многогранники с числом вершин более четырёх могут существовать только в пространствах размерности 4 и выше (и, в общем случае, k-смежностный многогранник, отличный от симплекса, требует размерности 2k и выше).

Произведение $P={\mathrm{\Delta <!--\; \Delta \; -->}}^2\times <!--\; \times \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}^2$$P=\Delta ^{2}\times \Delta ^{2}$  двух треугольников является простым многогранником и легко видеть, что любые две его гиперграни пересекаются по некоторой 2-грани. Таким образом, этот многогранник является двойственно 2-смежностным. Полярный многогранник $P^{\ast <!--\; \ast \; -->}$$P^*$  является смежностным симплициальным 4-многогранником.

d-Симплекс является d- смежностным многогранником.

В k-смежностном многограннике с $k⩾<!--\; ⩾\; -->3$$k\geqslant 3$ , любая 2-грань должна быть треугольной, а в k- смежностном многограннике с $k⩾<!--\; ⩾\; -->4$$k\geqslant 4$  любая 3-грань должна быть тетраэдром. В общем случае в любом k-смежностном многограннике все грани размерности меньшей k являются симплексами.

Циклические многогранникиПравить

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

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

Общие свойстваПравить

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

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

$f_{k-<!--\; -\; -->1}\le <!--\; \le \; -->\underset{i=0}{\overset{d/2}{\sum <!--\; \sum \; -->}}{}^{\ast <!--\; \ast \; -->}\left((\genfrac{}{}{0ex}{}{d-<!--\; -\; -->i}{k-<!--\; -\; -->i})+(\genfrac{}{}{0ex}{}{i}{k-<!--\; -\; -->d+i})\right)(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->d-<!--\; -\; -->1+i}{i}),$$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},$ 

где звёздочка означает прекращение суммирования на $i=\lfloor <!--\; \lfloor \; -->d/2\rfloor <!--\; \rfloor \; -->$$i=\lfloor d/2\rfloor$  и конечный член суммы должен быть поделён на два, если d чётно. Согласно теореме о верхней оценке^[en] Макмуллена, смежностные многогранники достигают максимального числа граней среди n-вершинных d-мерных выпуклых многогранников.

Обобщённая версия задачи со счастливым концом применяется к набору точек в пространстве высокой размерности и подразумевает, что для любой размерности d и любого n > d существует число m(d,n) со свойством, что любые m точек в общем положении в d-мерном пространстве содержит подмножество из n точек, образующих вершины смежностного многогранника

Гипотеза МаксименкоПравить

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