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

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

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

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

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

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

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

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

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

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