Grannpolytop

I geometri och polyedrisk kombinatorik är en k -neigborly polytop en konvex polytop där varje uppsättning av k eller färre hörn bildar ett ansikte . Till exempel är en 2-neigborly polytop en polytop där varje par av hörn är sammankopplade med en kant och bildar en komplett graf . 2-grannpolytoper med fler än fyra hörn kan endast existera i utrymmen med fyra eller fler dimensioner, och i allmänhet kräver en k -grannpolytop (annat än en simplex ) en dimension på 2 k eller mer. En d -simplex är d -grann. En polytop sägs vara granne , utan att specificera k , om den är k - grannliggande för k = ⌊ d ⁄ 2 ⌋ . Om vi ​​exkluderar simpliceringar är detta det maximala möjliga k : i själva verket är varje polytop som är k -grann för vissa k ≥ 1 + ⌊ d ⁄ 2 ⌋ en simplex.

I en k -grannpolytop med k ≥ 3 måste varje 2-yta vara en triangel, och i en k -grannpolytop med k ≥ 4 måste varje 3-yta vara en tetraeder. Mer generellt, i vilken k- grannpolytop som helst, är alla ytor med dimension mindre än k förenklade .

De cykliska polytoperna som bildas som de konvexa skroven av ändliga uppsättningar av punkter på momentkurvan ( t , t ² , …, t ^d ) i d -dimensionellt utrymme är automatiskt närliggande. Theodore Motzkin förmodade att alla närliggande polytoper är kombinatoriskt ekvivalenta med cykliska polytoper. Men i motsats till denna gissning finns det många grannpolytoper som inte är cykliska: antalet kombinatoriskt distinkta grannpolytoper växer superexponentiellt, både i antalet hörn av polytopen och i dimensionen.

Det konvexa skrovet av en uppsättning slumpmässiga punkter, ritat från en Gauss-fördelning med antalet punkter proportionellt mot dimensionen, är med stor sannolikhet k -grann för ett värde k som också är proportionellt mot dimensionen.

Antalet ytor av alla dimensioner av en närliggande polytop i ett jämnt antal dimensioner bestäms enbart från dess dimension och dess antal hörn av Dehn–Sommervilles ekvationer: antalet k - dimensionella ytor, f _k , uppfyller olikheten

$f_{k-1 }\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {di}{ki}}+{\binom {i}{k-d+i} }\right){\binom {nd-1+i}{i}},$

där asterisken betyder att summorna slutar på i = ⌊ d ⁄ 2 ⌋ och sluttermen för summan ska halveras om d är jämnt. Enligt den övre gränssatsen av McMullen (1970) uppnår grannpolytoper det maximala antalet ytor av varje n -vertex d -dimensionell konvex polytop.

En generaliserad version av problemet med lyckligt slut gäller för högre dimensionella punktuppsättningar, och antyder att det för varje dimension d och varje n > d finns ett tal m ( d , n ) med egenskapen att varje m pekar i allmän position i d -dimensionellt utrymme innehåller en delmängd av n punkter som bildar hörnen på en närliggande polytop.