Просмотр кода страницы Теорема о верхней границе

'''Теорема о верхней границе''' утверждает, что [[Циклический многогранник|циклические многогранники]] имеют наибольшее возможное число граней среди всех [[Выпуклый многогранник|выпуклых многогранников]] и [[Симплициальная сфера|триангуляций многомерной сферы]] при любой заданной размерности пространства и любом числе вершин.<ref name = A&K>{{Cite web |url=https://www.sciencedirect.com/science/article/pii/S0195669885800299#! |title=A Simple Proof of the Upper Bound Theorem - ScienceDirect |access-date=2022-11-16 |archive-date=2022-11-16 |archive-url=https://web.archive.org/web/20221116082019/https://www.sciencedirect.com/science/article/pii/S0195669885800299#! |deadlink=no }}</ref> Это один из важнейших результатов в [[Комбинаторика многогранников|комбинаторике многогранников]].

Первоначально утверждение было сформулировано {{не переведено 5|Моцкин, Теодор|Теодором Моцкиным||Theodore Motzkin}} для многогранников как '''гипотеза о верхней границе'''. Это утверждение доказано {{не переведено 5|Макмаллен, Питер|Питером Макмалленом||Peter McMullen}} в 1970 году.<ref>{{citation|title=Lectures on Polytopes|volume=152|series=Graduate Texts in Mathematics|first=Günter M.|last=Ziegler|publisher=Springer|year=1995|isbn=9780387943657|page=254|url=https://books.google.com/books?id=xd25TXSSUcgC&pg=PA254|quote=В 1970 Макмаллен доказал гипотезу невероятно простым и изящным способом.}}</ref> В 1975 году {{не переведено 5|Стенли, Ричард П.|Ричард Стенли||Richard P. Stanley}} обобщил утверждение теоремы на симплициальную сферу.<ref>{{cite book |title=Combinatorics and Commutative Algebra|last=Stanley|first=Richard|year=1996 |publisher=Birkhäuser Boston|location= Boston, Mass. |isbn=0-8176-3836-9 |pages=164}}</ref> В 1985 году [[Алон, Нога|Нога Алон]] и {{не переведено 5|Калаи,Гили|Гил Калаи||Gil Kalai}} дали простое доказательство теоремы в общем случае.<ref name = A&K />

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

: <math> f_i(\Delta(n,d)) = \binom{n}{i+1}</math> для <math>\quad 0 \leq i < \left\lfloor\frac{d}{2}\right\rfloor </math>

и <math>(f_0,\ldots,f_{\left\lfloor\frac{d}{2}\right\rfloor-1})</math> полностью определяет <math>(f_{\left\lfloor\frac{d}{2}\right\rfloor},\ldots,f_{d-1})</math> через [[уравнения Дена — Соммервиля]]. Такая же формула для числа граней верна для произвольного [[Смежностный многогранник|смежностного многогранника]].

== Теорема ==
Утверждается, что если <math>\Delta</math> многомерный выпуклый многогранник размерности <math>d</math> или симплициальная сфера размерности <math>d-1</math><ref>Размерность сферы на 1 меньше размерности многогранника.</ref> с <math>n</math> вершинами, то

: <math>f_i(\Delta) \leq f_i(\Delta(n,d))</math> для <math>\quad i=0,1,\ldots,d-1.</math>

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

== Следствия ==
Из теоремы вытекает, что выпуклая оболочка множества из <math>n</math> точек может быть построена алгоритмом сложности <math>O(n\log n)</math> в двумерном и трёхмерном пространстве и алгоритмом сложности <math>O(n^{\lfloor d/2\rfloor})</math> в пространствах более высокой размерности.<ref>{{citation
 | last = Chazelle | first = Bernard | author-link = Bernard Chazelle
 | doi = 10.1109/TIT.1985.1057060
 | issue = 4
 | journal = [[IEEE Transactions on Information Theory]]
 | mr = 798557
 | pages = 509–517
 | title = On the convex layers of a planar set
 | volume = 31
 | year = 1985}} 
</ref><ref>
{{citation
 | last1 = de Berg | first1 = M. | author1-link = Mark de Berg
 | last2 = van Kreveld | first2 = M. | author2-link = Marc van Kreveld
 | last3 = Overmars | first3 = Mark | author3-link = Mark Overmars
 | last4 = Schwarzkopf | first4 = O. | author4-link = Otfried Cheong
 | edition = 3rd
 | publisher = Springer
 | title = Computational Geometry: Algorithms and Applications
 | year = 2008}}
</ref>

== Примечания ==
{{Примечания}}

[[Категория:Комбинаторика многогранников]]