Teorema do limite superior - Upper bound theorem

Em matemática, o teorema do limite superior afirma que os politopos cíclicos têm o maior número possível de faces entre todos os politopos convexos com uma dada dimensão e número de vértices. É um dos resultados centrais da combinatória poliédrica .

Originalmente conhecida como conjectura do limite superior , esta afirmação foi formulada por Theodore Motzkin , provada em 1970 por Peter McMullen e reforçada de politopos a subdivisões de uma esfera em 1975 por Richard P. Stanley .

Politopos cíclicos

O politopo cíclico Δ ( n , d ) pode ser definido como o casco convexo de n vértices na curva de momento ( t ,  t ² ,  t ³ , ...). A escolha precisa de quais n pontos nesta curva são selecionados é irrelevante para a estrutura combinatória deste politopo. O número de faces i- dimensionais de Δ ( n , d ) é dado pela fórmula

${\ displaystyle f_ {i} (\ Delta (n, d)) = {\ binom {n} {i + 1}} \ quad {\ textrm {para}} \ quad 0 \ leq i <\ left \ lfloor { \ frac {d} {2}} \ right \ rfloor}$

e determinar completamente por meio das equações de Dehn-Sommerville . A mesma fórmula para o número de faces vale mais geralmente para qualquer politopo vizinho . ${\ displaystyle (f_ {0}, \ ldots, f _ {\ left \ lfloor {\ frac {d} {2}} \ right \ rfloor -1})}$${\ displaystyle (f _ {\ left \ lfloor {\ frac {d} {2}} \ right \ rfloor}, \ ldots, f_ {d-1})}$

Declaração

O teorema do limite superior afirma que se Δ é uma esfera simplicial de dimensão d - 1 com n vértices, então

${\ displaystyle f_ {i} (\ Delta) \ leq f_ {i} (\ Delta (n, d)) \ quad {\ textrm {para}} \ quad i = 0,1, \ ldots, d-1. }$

Ou seja, o número de faces de um politopo arbitrário nunca pode ser maior do que o número de faces de um politopo cíclico ou vizinho com a mesma dimensão e número de vértices. Assintoticamente, isso implica que existem no máximo faces de todas as dimensões. Os mesmos limites são válidos também para politopos convexos que não são simpliciais, pois perturbar os vértices de tal politopo (e tomar o casco convexo dos vértices perturbados) só pode aumentar o número de faces. ${\ displaystyle \ scriptstyle O (n ^ {\ lfloor d / 2 \ rfloor})}$

História

A conjectura do limite superior para politopos simpliciais foi proposta por Motzkin em 1957 e provada por McMullen em 1970. Um ingrediente-chave em sua prova foi a seguinte reformulação em termos de vetores- h :

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

Victor Klee sugeriu que a mesma afirmação deveria valer para todas as esferas simpliciais e isso foi de fato estabelecido em 1975 por Stanley usando a noção de um anel de Stanley-Reisner e métodos homológicos. Para um bom relato histórico deste teorema, veja.

Referências