Politopo vecino

En geometría y combinatoria poliédrica , un politopo k -vecino es un politopo convexo en el que cada conjunto de k o menos vértices forma una cara . Por ejemplo, un politopo 2-vecino es un politopo en el que cada par de vértices está conectado por una arista , formando un grafo completo . Los politopos 2-vecinos con más de cuatro vértices pueden existir solo en espacios de cuatro o más dimensiones, y en general un politopo k -vecino (distinto de un símplex ) requiere una dimensión de 2 k o más. Un d -símplex es d -vecino. Se dice que un politopo es vecino , sin especificar k , si es k -vecino para k = ⌊ d ⁄ 2 ⌋ . Si excluimos los símplices, este es el máximo k posible : de hecho, cada politopo que es k -vecino para algún k ≥ 1 + ⌊ d ⁄ 2 ⌋ es un símplex. ^[1]

En un politopo k -vecino con k ≥ 3 , cada 2-cara debe ser un triángulo, y en un politopo k -vecino con k ≥ 4 , cada 3-cara debe ser un tetraedro. De manera más general, en cualquier politopo k -vecino, todas las caras de dimensión menor que k son símplices .

Los politopos cíclicos formados como las envolturas convexas de conjuntos finitos de puntos en la curva de momentos ( t , t ² , …, t ^d ) en un espacio de dimensión d son automáticamente vecinos. Theodore Motzkin conjeturó que todos los politopos vecinos son combinatoriamente equivalentes a los politopos cíclicos. ^[2] Sin embargo, contrariamente a esta conjetura, hay muchos politopos vecinos que no son cíclicos: el número de politopos vecinos combinatoriamente distintos crece superexponencialmente, tanto en el número de vértices del politopo como en la dimensión. ^[3]

La envoltura convexa de un conjunto de puntos aleatorios, extraídos de una distribución gaussiana con un número de puntos proporcional a la dimensión, es con alta probabilidad k -vecina para un valor k que también es proporcional a la dimensión. ^[4]

El número de caras de todas las dimensiones de un politopo vecino en un número par de dimensiones se determina únicamente a partir de su dimensión y su número de vértices mediante las ecuaciones de Dehn-Sommerville : el número de caras k -dimensionales, f _k , satisface la desigualdad

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

donde el asterisco significa que la suma termina en i = ⌊ d ⁄ 2 ⌋ y el término final de la suma debe reducirse a la mitad si d es par. ^[5] Según el teorema del límite superior de McMullen (1970), ^[6] los politopos vecinos logran el máximo número posible de caras de cualquier politopo convexo de dimensión d y n vértices .

Una versión generalizada del problema del final feliz se aplica a conjuntos de puntos de dimensiones superiores e implica que para cada dimensión d y cada n > d existe un número m ( d , n ) con la propiedad de que cada m puntos en posición general en el espacio d -dimensional contiene un subconjunto de n puntos que forman los vértices de un politopo vecino. ^[7]