PROFILPELAJAR.COM

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

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

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

Циклический многогранник $\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$ ^[4] с $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 })$ в пространствах более высокой размерности.^[5]^[6]

Примечания

↑ ¹ ² 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