La combinatoria poliédrica es una rama de las matemáticas , dentro de la combinatoria y la geometría discreta , que estudia los problemas de contar y describir las caras de poliedros convexos y politopos convexos de dimensiones superiores .
La investigación en combinatoria poliédrica se divide en dos áreas distintas. Los matemáticos de esta área estudian la combinatoria de politopos; por ejemplo, buscan desigualdades que describan las relaciones entre los números de vértices , aristas y caras de dimensiones superiores en politopos arbitrarios o en ciertas subclases importantes de politopos, y estudian otras propiedades combinatorias de los politopos, como su conectividad y diámetro (número de pasos necesarios para llegar a cualquier vértice desde cualquier otro vértice). Además, muchos científicos informáticos utilizan la frase "combinatoria poliédrica" para describir la investigación sobre descripciones precisas de las caras de ciertos politopos específicos (especialmente politopos 0-1, cuyos vértices son subconjuntos de un hipercubo ) que surgen de problemas de programación entera .
Una cara de un politopo convexo P puede definirse como la intersección de P y un semiespacio cerrado H tal que el límite de H no contiene ningún punto interior de P . La dimensión de una cara es la dimensión de esta envoltura. Las caras de dimensión 0 son los propios vértices, y las caras de dimensión 1 (llamadas aristas ) son segmentos de línea que conectan pares de vértices. Nótese que esta definición también incluye como caras el conjunto vacío y el politopo entero P . Si P en sí tiene dimensión d , las caras de P con dimensión d − 1 se llaman facetas de P y las caras con dimensión d − 2 se llaman crestas . [1] Las caras de P pueden ordenarse parcialmente por inclusión, formando una red de caras que tiene como elemento superior al propio P y como elemento inferior al conjunto vacío.
Una herramienta clave en la combinatoria poliédrica es el ƒ-vector de un politopo, [2] el vector ( f 0 , f 1 , ..., f d − 1 ) donde f i es el número de características i -dimensionales del politopo. Por ejemplo, un cubo tiene ocho vértices, doce aristas y seis facetas, por lo que su ƒ-vector es (8,12,6). El politopo dual tiene un ƒ-vector con los mismos números en orden inverso; así, por ejemplo, el octaedro regular , el dual de un cubo, tiene el ƒ-vector (6,12,8). Las matrices de configuración incluyen los f-vectores de politopos regulares como elementos diagonales.
El vector ƒ extendido se forma concatenando el número uno en cada extremo del vector ƒ, contando el número de objetos en todos los niveles de la red de caras; en el lado izquierdo del vector, f −1 = 1 cuenta el conjunto vacío como una cara, mientras que en el lado derecho, f d = 1 cuenta a P en sí. Para el cubo, el vector ƒ extendido es (1,8,12,6,1) y para el octaedro es (1,6,12,8,1). Aunque los vectores para estos poliedros de ejemplo son unimodales (los coeficientes, tomados en orden de izquierda a derecha, aumentan hasta un máximo y luego disminuyen), hay politopos de dimensiones superiores para los que esto no es cierto. [3]
Para politopos simpliciales (politopos en los que cada faceta es un símplex ), a menudo es conveniente transformar estos vectores, produciendo un vector diferente llamado h -vector. Si interpretamos los términos del ƒ-vector (omitiendo el 1 final) como coeficientes de un polinomio ƒ( x ) = Σ f i x d − i − 1 (por ejemplo, para el octaedro esto da el polinomio ƒ( x ) = x 3 + 6 x 2 + 12 x + 8), entonces el h -vector enumera los coeficientes del polinomio h ( x ) = ƒ( x − 1) (de nuevo, para el octaedro, h ( x ) = x 3 + 3 x 2 + 3 x + 1). [4] Como escribe Ziegler, “para varios problemas sobre politopos simples, los h -vectores son una forma mucho más conveniente y concisa de codificar la información sobre los números de las caras que los ƒ-vectores”.
La relación más importante entre los coeficientes del vector ƒ de un politopo es la fórmula de Euler Σ(−1) i f i = 0, donde los términos de la suma abarcan los coeficientes del vector ƒ extendido. En tres dimensiones, mover los dos 1 en los extremos izquierdo y derecho del vector ƒ extendido (1, v , e , f , 1) al lado derecho de la ecuación transforma esta identidad en la forma más familiar v − e + f = 2. Del hecho de que cada faceta de un poliedro tridimensional tiene al menos tres aristas, se deduce por doble conteo que 2 e ≥ 3 f , y usar esta desigualdad para eliminar e y f de la fórmula de Euler conduce a las desigualdades adicionales e ≤ 3 v − 6 y f ≤ 2 v − 4. Por dualidad, e ≤ 3 f − 6 y v ≤ 2 f − 4. Se deduce del teorema de Steinitz que cualquier vector entero tridimensional que satisfaga estas igualdades y desigualdades es el vector ƒ de un poliedro convexo. [5]
En dimensiones superiores, otras relaciones entre los números de caras de un politopo también se vuelven importantes, incluidas las ecuaciones de Dehn-Sommerville que, expresadas en términos de h -vectores de politopos simpliciales, toman la forma simple h k = h d − k para todo k . La instancia de estas ecuaciones con k = 0 es equivalente a la fórmula de Euler pero para d > 3 las otras instancias de estas ecuaciones son linealmente independientes entre sí y restringen los h -vectores (y por lo tanto también los ƒ-vectores) de maneras adicionales. [4]
Otra desigualdad importante en el número de caras de un politopo está dada por el teorema del límite superior , demostrado por primera vez por McMullen (1970), que establece que un politopo de dimensión d con n vértices puede tener como máximo tantas caras de cualquier otra dimensión como un politopo vecino con el mismo número de vértices:
donde el asterisco significa que el término final de la suma debe reducirse a la mitad cuando d es par. [6] Asintóticamente, esto implica que hay como máximo caras de todas las dimensiones.
Incluso en cuatro dimensiones, el conjunto de posibles vectores ƒ de politopos convexos no forma un subconjunto convexo de la red entera de cuatro dimensiones, y aún queda mucho por saber acerca de los posibles valores de estos vectores. [7]
Además de investigar el número de caras de los politopos, los investigadores han estudiado otras propiedades combinatorias de los mismos, como las descripciones de los gráficos obtenidos a partir de los vértices y aristas de los politopos (su 1-esqueleto ).
El teorema de Balinski establece que el grafo obtenido de esta manera a partir de cualquier politopo convexo de dimensión d es conexo por vértices d . [8] En el caso de poliedros tridimensionales, esta propiedad y la planaridad se pueden utilizar para caracterizar exactamente los grafos de los poliedros: el teorema de Steinitz establece que G es el esqueleto de un poliedro tridimensional si y solo si G es un grafo plano conexo por 3 vértices. [9]
Un teorema de Blind y Mani-Levitska (1987) (conjeturado previamente por Micha Perles ) establece que se puede reconstruir la estructura de caras de un politopo simple a partir de su grafo. Es decir, si un grafo no dirigido dado es el esqueleto de un politopo simple, solo hay un politopo (hasta la equivalencia combinatoria) para el cual esto es cierto. Esto está en marcado contraste con los politopos vecinos (no simples) cuyo grafo es un grafo completo ; puede haber muchos politopos vecinos diferentes para el mismo grafo. Otra prueba de este teorema basada en orientaciones de sumidero únicas fue dada por Kalai (1988), y Friedman (2009) mostró cómo usar este teorema para derivar un algoritmo de tiempo polinomial para reconstruir las redes de caras de politopos simples a partir de sus grafos. Sin embargo, probar si un gráfico o red dado puede realizarse como la red de caras de un politopo simple es equivalente (por polaridad) a la realización de politopos simpliciales , lo cual se demostró que era completo para la teoría existencial de los reales por Adiprasito y Padrol (2017).
En el contexto del método símplex para programación lineal , es importante entender el diámetro de un politopo, el número mínimo de aristas necesarias para alcanzar cualquier vértice por un camino desde cualquier otro vértice. El sistema de desigualdades lineales de un programa lineal define facetas de un politopo que representan todas las soluciones factibles para el programa, y el método símplex encuentra la solución óptima siguiendo un camino en este politopo. Por lo tanto, el diámetro proporciona un límite inferior en el número de pasos que requiere este método. La conjetura de Hirsch , ahora refutada, sugirió un límite fuerte (lineal) sobre cuán grande podría ser el diámetro de un politopo con dimensión fija y número de facetas . [10] Se conocen límites superiores más débiles (cuasi-polinomiales en y ) en su diámetro, [11] así como pruebas de la conjetura de Hirsch para clases especiales de politopos. [12]
Decidir si el número de vértices de un politopo dado está limitado por algún número natural k es un problema computacionalmente difícil y completo para la clase de complejidad PP . [13]
En el contexto de los métodos de plano de corte para la programación entera, es importante poder describir con precisión las facetas de los politopos que tienen vértices correspondientes a las soluciones de los problemas de optimización combinatoria. A menudo, estos problemas tienen soluciones que se pueden describir mediante vectores binarios y los politopos correspondientes tienen coordenadas de vértice que son todas cero o uno.
Como ejemplo, considere el politopo de Birkhoff , el conjunto de matrices n × n que se pueden formar a partir de combinaciones convexas de matrices de permutación . Equivalentemente, sus vértices pueden considerarse como la descripción de todos los emparejamientos perfectos en un grafo bipartito completo , y un problema de optimización lineal en este politopo puede interpretarse como un problema de emparejamiento perfecto de peso mínimo bipartito. El teorema de Birkhoff-von Neumann establece que este politopo puede describirse mediante dos tipos de desigualdad o igualdad lineal. Primero, para cada celda de la matriz, existe una restricción de que esta celda tiene un valor no negativo. Y segundo, para cada fila o columna de la matriz, existe una restricción de que la suma de las celdas en esa fila o columna es igual a uno. Las restricciones de fila y columna definen un subespacio lineal de dimensión n 2 − 2 n + 1 en el que se encuentra el politopo de Birkhoff, y las restricciones de no negatividad definen facetas del politopo de Birkhoff dentro de ese subespacio.
Sin embargo, el politopo de Birkhoff es inusual porque se dispone de una descripción completa de sus facetas. Para muchos otros politopos 0-1, hay exponencialmente muchas o superexponencialmente muchas facetas, y solo se dispone de descripciones parciales de sus facetas. [14]
