Övre gränssats

Inom matematiken säger den övre gränssatsen att cykliska polytoper har största möjliga antal ytor bland alla konvexa polytoper med en given dimension och antal hörn. Det är ett av de centrala resultaten av polyedrisk kombinatorik .

Ursprungligen känd som den övre gränsen förmodan , detta uttalande formulerades av Theodore Motzkin , bevisades 1970 av Peter McMullen och stärktes från polytoper till underavdelningar av en sfär 1975 av Richard P. Stanley .

Cykliska polytoper

Huvudartikel: Cyklisk polytop

Den cykliska polytopen $\Delta (n,d)$ kan definieras som det konvexa skrovet av $n$ hörn på momentkurvan , mängden $d$ - dimensionella punkter med koordinater $(t,t^{2},t^{3},\dots )$ . Det exakta valet av vilka $n$ punkter på denna kurva som väljs är irrelevant för den kombinatoriska strukturen för denna polytop. Antalet $i$ -dimensionella ytor av $\Delta (n,d)$ ges av formeln

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

och $(f_{0},\ldots ,f_{\left\lfloor {\frac {d}{2}}\right\rfloor -1})$ bestämma fullständigt $(f_{\left\lfloor {\frac {d}{2}}\right\rfloor },\ldots ,f_{d- 1})$ via Dehn–Sommerville-ekvationerna . Samma formel för antalet ansikten gäller mer generellt för alla grannpolytoper .

Påstående

Den övre gränssatsen säger att om $\Delta$ är en enkel sfär med dimensionen $d-1$ med $n$ hörn, då

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

Skillnaden mellan $d-1$ för dimensionen av den enkla sfären, och $d$ för dimensionen av den cykliska polytopen, kommer från det faktum att ytan på en $d$ -dimensionell polytop (som den cykliska polytopen) är en $(d-1)$ -dimensionell underavdelning av en sfär. Därför innebär den övre gränssatsen att antalet ytor av en godtycklig polytop aldrig kan vara fler än antalet ytor av en cyklisk eller grannpolytop med samma dimension och antal hörn. Asymptotiskt innebär detta att det finns högst $\scriptstyle O(n^{\lfloor d/2\rfloor })$ ytor av alla dimensioner. Samma gränser gäller även för konvexa polytoper som inte är enkla, eftersom att störa hörnen på en sådan polytop (och ta det konvexa skrovet på de störda hörnen) bara kan öka antalet ytor.

Historia

Den övre gränsen gissningen för enkla polytoper föreslogs av Motzkin 1957 och bevisades av McMullen 1970. En nyckelingrediens i hans bevis var följande omformulering i termer av h -vektorer :

$h_{i}(\Delta )\leq {\tbinom {n-d+i-1}{i}}\quad {\textrm {for}}\quad 0\leq i<\left\lfloor { \frac {d}{2}}\höger\rgolv .$

Victor Klee föreslog att samma uttalande skulle gälla för alla enkla sfärer och detta etablerades verkligen 1975 av Stanley med hjälp av tanken om en Stanley-Reisner-ring och homologiska metoder. För en trevlig historisk redogörelse för detta teorem, se Stanleys artikel "How the upper bound conjecture was proved".