Теорема о верхней оценке

В математике теорема о верхней границе утверждает, что циклические многогранники имеют максимально возможное количество граней среди всех выпуклых многогранников с заданной размерностью и количеством вершин. Это один из центральных результатов полиэдральной комбинаторики .

Первоначально известное как гипотеза о верхней границе , это утверждение было сформулировано Теодором Моцкиным и доказано в 1970 году Питером Макмалленом . и усилен от многогранников к подразделениям сферы в 1975 году Ричардом П. Стэнли .

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

Основная статья: Циклический многогранник

Циклический многогранник $\Delta (n,d)$ можно определить как выпуклую оболочку $n$ вершин на кривой момента , множество $d$-мерные точки с координатами $(t,t^{2},t^{3},\dots )$. Точный выбор того, что $n$ точки на этой кривой не имеют значения для комбинаторного строения этого многогранника.Количество $i$-мерные грани $\Delta (n,d)$ определяется формулой $$f_{i}(\Delta (n,d))={\binom {n}{i+1}}\quad {\textrm {for}}\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-1$ с $n$ вершины, то $$f_{i}(\Delta )\leq f_{i}(\Delta (n,d))\quad {\textrm {for}}\quad i=0,1,\ldots ,d-1.$$Разница между $d-1$ для размерности симплициальной сферы и $d$ для размерности циклического многогранника исходит из того факта, что поверхность $d$-мерный многогранник (например, циклический многогранник) — это $(d-1)$-мерное подразделение сферы.Следовательно, из теоремы о верхней оценке следует, что количество граней произвольного многогранника никогда не может быть больше количества граней циклического или соседнего многогранника с той же размерностью и числом вершин.Асимптотически это означает, что существует не более $\scriptstyle O(n^{\lfloor d/2\rfloor })$ лица всех размеров.Те же оценки справедливы и для выпуклых многогранников, которые не являются симплициальными, поскольку возмущение вершин такого многогранника (и взятие выпуклой оболочки возмущенных вершин) может только увеличить количество граней.

История

Гипотеза о верхней границе для симплициальных многогранников была предложена Моцкиным в 1957 году и доказана Макмалленом в 1970 году. Ключевым моментом в его доказательстве была следующая переформулировка в терминах h -векторов :

$h_{i}(\Delta )\leq {\tbinom {n-d+i-1}{i}}\quad {\textrm {for}}\quad 0\leq i\leq \left\lfloor {\frac {d}{2}}\right\rfloor .$

Виктор Клее предположил, что одно и то же утверждение должно быть справедливым для всех симплициальных сфер, и это действительно было установлено в 1975 году Стэнли. используя понятие кольца Стэнли–Рейснера и гомологические методы. Хороший исторический обзор этой теоремы см. в статье Стэнли «Как была доказана гипотеза о верхней границе».