Теорема о верхней границе
Теорема о верхней границе утверждает, что циклические многогранники имеют наибольшее возможное число граней среди всех выпуклых многогранников и триангуляций многомерной сферы при любой заданной размерности пространства и любом числе вершин.[1] Это один из важнейших результатов в комбинаторике многогранников.
Первоначально утверждение было сформулировано Теодором Моцкиным[англ.] для многогранников как гипотеза о верхней границе. Это утверждение доказано Питером Макмалленом[англ.] в 1970 году.[2] В 1975 году Ричард Стенли[англ.] обобщил утверждение теоремы на симплициальную сферу.[3] В 1985 году Нога Алон и Гил Калаи[англ.] дали простое доказательство теоремы в общем случае.[1]
Циклические многогранники
[править | править код]Циклический многогранник это выпуклая оболочка вершин, которые заданы кривой моментов — множество -мерных точек с координатами . Конкретный выбор точек на кривой не влияет на комбинаторную структуру многогранника. Число -мерных граней задаётся формулой
- для
и полностью определяет через уравнения Дена — Соммервиля. Такая же формула для числа граней верна для произвольного смежностного многогранника.
Теорема
[править | править код]Утверждается, что если многомерный выпуклый многогранник размерности или симплициальная сфера размерности [4] с вершинами, то
- для
Иначе говоря теорема утверждает, что независимо от размерности пространства число граней выпуклого многогранника не может быть больше, чем число граней циклического многогранника с тем же числом вершин. Асимптотически это означает, что многомерные выпуклые многогранники имеют граней.
Следствия
[править | править код]Из теоремы вытекает, что выпуклая оболочка множества из точек может быть построена алгоритмом сложности в двумерном и трёхмерном пространстве и алгоритмом сложности в пространствах более высокой размерности.[5][6]
Примечания
[править | править код]- ↑ 1 2 A Simple Proof of the Upper Bound Theorem - ScienceDirect . Дата обращения: 16 ноября 2022. Архивировано 16 ноября 2022 года.
- ↑ Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer, p. 254, ISBN 9780387943657,
В 1970 Макмаллен доказал гипотезу невероятно простым и изящным способом.
- ↑ Stanley, Richard. Combinatorics and Commutative Algebra. — Boston, Mass. : Birkhäuser Boston, 1996. — P. 164. — ISBN 0-8176-3836-9.
- ↑ Размерность сферы на 1 меньше размерности многогранника.
- ↑ Chazelle, Bernard (1985), "On the convex layers of a planar set", IEEE Transactions on Information Theory, 31 (4): 509—517, doi:10.1109/TIT.1985.1057060, MR 0798557
- ↑ de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. (2008), Computational Geometry: Algorithms and Applications (3rd ed.), Springer