Соседний многогранник

В геометрии и многогранной комбинаторике — k -соседний многогранник это выпуклый многогранник , в котором каждый набор из k или меньшего числа вершин образует грань . Например, многогранник с 2 соседями — это многогранник, в котором каждая пара вершин соединена ребром , образуя полный граф . 2-соседние многогранники с более чем четырьмя вершинами могут существовать только в пространствах четырех или более измерений, и вообще k -соседний многогранник (кроме симплекса ) требует размерности 2 k или более. D - симплекс является d -соседним. Многогранник называется соседним без указания k , если он является k -соседним для k = ⌊ д ⁄ 2 ⌋ . Если исключить симплексы, это будет максимально возможное k : фактически, каждый многогранник, являющийся k -соседним для некоторого k ≥ 1 + ⌊ d ⁄ 2 ⌋ — симплекс.

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

Циклические многогранники образовывались как выпуклые оболочки конечных наборов точек на кривой моментов ( t , t ² , …, т ^д ) в d -мерном пространстве автоматически соседствуют. Теодор Моцкин предположил, что все соседние многогранники комбинаторно эквивалентны циклическим многогранникам. Однако, вопреки этой гипотезе, существует множество соседних многогранников, которые не являются циклическими: число комбинаторно различных соседних многогранников растет суперэкспоненциально, как по числу вершин многогранника, так и по размерности.

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

Число граней всех измерений соседнего многогранника в четном числе измерений определяется исключительно его размерностью и количеством вершин уравнениями – Соммервилля : число k -мерных граней fk _Дена удовлетворяет неравенству

$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 = ⌊ d ⁄ 2 ⌋ и последний член суммы следует уменьшить вдвое, если d четное. Согласно верхней границе о теореме Макмаллена (1970) , соседние многогранники достигают максимально возможного числа граней любого n -вершинного d -мерного выпуклого многогранника.

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