Combinatoria poliédrica

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 el número 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 alcanzar cualquier vértice desde cualquier otro). Además, muchos informáticos utilizan la expresión "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 se puede definir como la intersección de P y un semiplano 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 vértices mismos, 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 todo el politopo P. Si P mismo 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 aristas . ^{[ 1 ]} Las caras de P pueden estar parcialmente ordenadas por inclusión, formando una red de caras que tiene como su elemento superior a P mismo y como su elemento inferior al conjunto vacío.    

Una herramienta clave en combinatoria poliédrica es el vector ƒ de un politopo, ^{[ 2 ]} el vector ( f ₀ , f ₁ , ..., 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 caras, 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 vectores f 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 cuenta el conjunto vacío como una cara, mientras que en el lado derecho, f _d  =  1 cuenta P mismo. 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), existen politopos de dimensiones superiores para los que esto no es cierto. ^{[ 3 ]}

Para politopos simpliciales (politopos en los que cada faceta es un simplex ), a menudo es conveniente transformar estos vectores, produciendo un vector diferente llamado vector h . 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 ³ + 6 x ² + 12 x + 8), entonces el vector h enumera los coeficientes del polinomio h ( x ) = ƒ( x − 1) (nuevamente, para el octaedro, h ( x ) = x ³ + 3 x ² + 3 x + 1). ^{[ 4 ]} Como escribe Ziegler, “para varios problemas sobre politopos simpliciales, los h -vectores son una forma mucho más conveniente y concisa de codificar la información sobre los números de 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) ⁱ f _i = 0, donde los términos de la suma abarcan los coeficientes del vector ƒ extendido. En tres dimensiones, al mover los dos 1 de los extremos izquierdo y derecho del vector ƒ extendido (1, v , e , f , 1) al lado derecho de la ecuación, esta identidad se transforma 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 usando esta desigualdad para eliminar e y f de la fórmula de Euler se obtienen las desigualdades adicionales e ≤ 3 v − 6 y f ≤ 2 v − 4 . Por dualidad, e ≤ 3 f − 6 y v ≤ 2 f − 4. Del teorema de Steinitz se deduce 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 el número de caras de un politopo también se vuelven importantes, incluyendo 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 sobre el número de caras de un politopo viene dada por el teorema del límite superior , demostrado por primera vez por McMullen (1970) , que establece que un politopo d -dimensional 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:

${\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 el último término de la suma debe dividirse por la mitad cuando d es par. ^{[ 6 ]} Asintóticamente, esto implica que hay como máximo${\displaystyle \scriptstyle O(n^{\lfloor d/2\rfloor })}$rostros 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 se desconoce mucho sobre 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 grafos obtenidos a partir de los vértices y las 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 d -dimensional es d -conexo por vértices . ^{[ 8 ]} En el caso de poliedros tridimensionales, esta propiedad y la planaridad pueden usarse para caracterizar exactamente los grafos de poliedros: el teorema de Steinitz establece que G es el esqueleto de un poliedro tridimensional si y solo si G es un grafo planar 3-conexo por vértices. ^{[ 9 ]}

Un teorema de Blind y Mani-Levitska (1987) (previamente conjeturado por Micha Perles ) afirma 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, existe un único politopo (salvo equivalencia combinatoria) para el cual esto es cierto. Esto contrasta notablemente con los politopos vecinos (no simples) cuyo grafo es un grafo completo ; puede haber muchos politopos vecinos diferentes para el mismo grafo. Kalai (1988) presentó otra demostración de este teorema basada en orientaciones únicas de sumideros , y Friedman (2009) mostró cómo utilizar 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 grafo o retículo dado puede realizarse como el retículo de caras de un politopo simple es equivalente (por polaridad) a la realización de politopos simpliciales , lo cual fue demostrado como completo para la teoría existencial de los reales por Adiprasito y Padrol (2017) .

En el contexto del método simplex para la programación lineal , es importante comprender el diámetro de un politopo, el número mínimo de aristas necesarias para alcanzar cualquier vértice mediante 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 del programa, y ​​el método simplex encuentra la solución óptima siguiendo un camino en este politopo. Por lo tanto, el diámetro proporciona una cota inferior para el número de pasos que requiere este método. La conjetura de Hirsch , ahora refutada, sugería una cota fuerte (lineal) para el tamaño máximo del diámetro de un politopo con dimensión fija.${\displaystyle d}$y número de facetas${\displaystyle n}$podría ser. ^{[ 10 ]} Más débil (cuasi-polinomial en${\displaystyle d}$y${\displaystyle n}$) se conocen cotas superiores para su diámetro, ^{[ 11 ]} así como demostraciones de la conjetura de Hirsch para clases especiales de politopos. ^{[ 12 ]}

Decidir si el número de vértices de un politopo dado está acotado 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 planos de corte para la programación entera, es importante poder describir con precisión las facetas de los politopos cuyos vértices corresponden a las soluciones de problemas de optimización combinatoria. A menudo, estos problemas tienen soluciones que pueden describirse mediante vectores binarios , y los politopos correspondientes tienen coordenadas de vértice iguales a cero o uno.

Como ejemplo, consideremos el politopo de Birkhoff , el conjunto de matrices n × n que se pueden formar a partir de combinaciones convexas de matrices de permutación . De forma equivalente, sus vértices pueden interpretarse 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 la restricción de que esta celda tenga un valor no negativo. Y segundo, para cada fila o columna de la matriz, existe la restricción de que la suma de las celdas en esa fila o columna sea igual a uno. Las restricciones de filas y columnas definen un subespacio lineal de dimensión n² − 2n + 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, existen un número exponencial o superexponencial de facetas, y solo se dispone de descripciones parciales de las mismas. ^{[ 14 ]}

• Polítopo abstracto
• Álgebra conmutativa combinatoria
• politopo matroide
• politopo de orden
• esfera simplicial
• Politopo de coincidencia estable

• Kalai, Gil (2008), Cinco problemas abiertos sobre politopos convexos.