Теорема о верхней границе утверждает, что циклические многогранники имеют наибольшее возможное число граней среди всех выпуклых многогранников и триангуляций многомерной сферы при любой заданной размерности пространства и любом числе вершин. Это один из важнейших результатов в комбинаторике многогранников.
Первоначально утверждение было сформулировано для многогранников как гипотеза о верхней границе. Это утверждение доказано в 1970 году. В 1975 году обобщил утверждение теоремы на симплициальную сферу. В 1985 году Нога Алон и дали простое доказательство теоремы в общем случае.
Циклические многогранники
Циклический многогранник это выпуклая оболочка вершин, которые заданы кривой моментов — множество -мерных точек с координатами . Конкретный выбор точек на кривой не влияет на комбинаторную структуру многогранника. Число -мерных граней задаётся формулой
для
и полностью определяет через уравнения Дена — Соммервиля. Такая же формула для числа граней верна для произвольного смежностного многогранника.
Теорема Утверждается, что если многомерный выпуклый многогранник размерности или симплициальная сфера размерности Размерность сферы на 1 меньше размерности многогранника. с вершинами, то
для
Иначе говоря теорема утверждает, что независимо от размерности пространства число граней выпуклого многогранника не может быть больше, чем число граней циклического многогранника с тем же числом вершин. Асимптотически это означает, что многомерные выпуклые многогранники имеют граней.
Следствия Из теоремы вытекает, что выпуклая оболочка множества из точек может быть построена алгоритмом сложности в двумерном и трёхмерном пространстве и алгоритмом сложности в пространствах более высокой размерности.
Примечания
Категория:Комбинаторика многогранников