Теорема о верхней границе

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

Первоначально утверждение было сформулировано Теодором Моцкиным для многогранников как гипотеза о верхней границе. Это утверждение доказано Питером Макмалленом в 1970 году. В 1975 году Ричард Стенли обобщил утверждение теоремы на симплициальную сферу. В 1985 году Нога Алон и Гил Калаи дали простое доказательство теоремы в общем случае.

Циклические многогранники

Основная статья: Циклический многогранник

Циклический многогранник $\Delta (n,d)$ это выпуклая оболочка $n$ вершин, которые заданы кривой моментов — множество $d$-мерных точек с координатами $(t,t^{2},t^{3},\dots )$. Конкретный выбор точек на кривой не влияет на комбинаторную структуру многогранника. Число $i$-мерных граней $\Delta (n,d)$ задаётся формулой

$f_{i}(\Delta (n,d))={\binom {n}{i+1}}$ для $\quad 0\leq i<\left\lfloor {\frac {d}{2}}\right\rfloor$

и $(f_{0},\ldots ,f_{\left\lfloor {\frac {d}{2}}\right\rfloor -1})$ полностью определяет $(f_{\left\lfloor {\frac {d}{2}}\right\rfloor },\ldots ,f_{d-1})$ через уравнения Дена — Соммервиля. Такая же формула для числа граней верна для произвольного смежностного многогранника.

Теорема

Утверждается, что если $\Delta$ многомерный выпуклый многогранник размерности $d$ или симплициальная сфера размерности $d-1$ с $n$ вершинами, то

$f_{i}(\Delta )\leq f_{i}(\Delta (n,d))$ для $\quad i=0,1,\ldots ,d-1.$

Иначе говоря теорема утверждает, что независимо от размерности пространства число граней выпуклого многогранника не может быть больше, чем число граней циклического многогранника с тем же числом вершин. Асимптотически это означает, что многомерные выпуклые многогранники имеют $O(n^{\lfloor d/2\rfloor })$ граней.

Следствия

Из теоремы вытекает, что выпуклая оболочка множества из $n$ точек может быть построена алгоритмом сложности $O(n\log n)$ в двумерном и трёхмерном пространстве и алгоритмом сложности $O(n^{\lfloor d/2\rfloor })$ в пространствах более высокой размерности.