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

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

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

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

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

$f_i(\mathrm{\Delta }(n,d))=(\genfrac{}{}{0ex}{}{n}{i+1})$ для $0\le i<\lfloor \frac{d}{2}\rfloor$

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

Теорема

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

$f_i(\mathrm{\Delta })\le f_i(\mathrm{\Delta }(n,d))$ для $i=0,1,\dots ,d-1.$

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

Следствия

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