Combinatoria de poliedros

La combinatoria de poliedros  es una rama de las matemáticas que pertenece a la combinatoria y la geometría combinatoria y estudia los problemas de contar y describir las caras de los poliedros convexos .

La investigación en la combinatoria de poliedros se divide en dos ramas. Los matemáticos que trabajan en este campo estudian la combinatoria de poliedros; por ejemplo, buscan desigualdades que describen la relación entre el número de vértices, aristas y caras de diferentes dimensiones en un poliedro arbitrario y también estudian otras propiedades combinatorias de los poliedros, como la conectividad y el diámetro (el 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 de poliedros" para describir la investigación sobre la descripción exacta de las caras de ciertos poliedros (especialmente poliedros 0-1, cuyos vértices son subconjuntos del hipercubo ) que surgen de problemas de programación entera .

Caras y vectores de conteo de caras

Una cara de un poliedro convexo P se puede definir como la intersección de P y un semiespacio cerrado H tal que el límite de H no contiene puntos interiores de P. La dimensión de una cara es igual a la dimensión de esta intersección. Las caras de dimensión 0 son los vértices mismos, mientras que las caras de dimensión 1 (llamadas aristas ) son segmentos de línea que conectan pares de vértices. Tenga en cuenta que esta definición incluye conjuntos vacíos y todo el politopo P como caras . Si P tiene dimensión d , las caras de P con dimensión d  − 1 se denominan facetas de P , y las caras de dimensión d  − 2 se denominan crestas [1] . Las caras de P se pueden ordenar parcialmente por inclusión, formando una red de caras con el propio poliedro P en la parte superior y el conjunto vacío en la parte inferior.

El método clave de la combinatoria de politopos es la consideración del vector ƒ del politopo [2]  — el vector ( f 0 , f 1 , …, f d  − 1 ), donde f i es el número de caras i -dimensionales del politopo. Por ejemplo, un cubo tiene ocho vértices, doce aristas y seis caras (biseles), por lo que su vector ƒ es (8,12,6). El poliedro dual tiene un vector ƒ con los mismos números en orden inverso. Entonces, por ejemplo, el octaedro regular , dual al cubo, tiene el vector ƒ (6,12,8). El vector ƒ extendido se forma sumando unos a ambos extremos del vector ƒ, lo que corresponde a la enumeración de objetos de todos los niveles de la red de caras: f −1  = 1 refleja el conjunto vacío como una cara, mientras que f d  = 1 refleja P mismo . Para un cubo, el vector f extendido es (1,8,12,6,1), y para un octaedro es (1,6,12,8,1). Aunque los vectores de estos ejemplos son unimodales (los elementos de izquierda a derecha primero aumentan y luego disminuyen), hay poliedros de dimensiones superiores para los que esto no es cierto [3] .

Para politopos simpliciales (politopos en los que cada cara es un símplex ), este vector a menudo se transforma para formar un vector h . Si consideramos los elementos del vector ƒ (sin un 1 finito) como los coeficientes del polinomio ƒ( x ) = Σ f i x d  −  i  − 1 (por ejemplo, para un octaedro esto da el polinomio ƒ( x ) =  x 3  + 6 x 2  + 12 x  + 8), entonces el vector h contiene los coeficientes del polinomio h ( x ) = ƒ( x  − 1) (nuevamente, para un octaedro, h ( x ) =  x 3  + 3 x 2  + 3 x  + 1) [4] . Como escribe Ziegler, "para varios problemas sobre politopos simpliciales, los vectores h son mucho más convenientes para dar información sobre el número de caras que los vectores f".

Igualdades y desigualdades

La relación más importante de los coeficientes del vector ƒ de un poliedro es la fórmula de Euler Σ(−1) i f i = 0, donde la suma es sobre los elementos del vector ƒ extendido. En tres dimensiones, mover dos 1 desde los lados izquierdo y derecho del vector ƒ extendido (1, v , e , f , 1) al lado derecho de la igualdad transforma la igualdad en el más familiar v − e + f = 2. Del hecho de que cualquier cara de un poliedro 3D tiene al menos tres aristas, se sigue que 2 e ≥ 3 f . Usando esta expresión para eliminar e y f de la fórmula de Euler, obtenemos e ≤ 3 v − 6 y f ≤ 2 v − 4. Debido a la dualidad de e ≤ 3 f − 6 y v ≤ 2 f − 4. El teorema de Steinitz implica que cualquier vector entero tridimensional que satisfaga estas igualdades y desigualdades es el vector ƒ de un poliedro convexo [5] .

En dimensiones superiores, se vuelven importantes otras relaciones entre el número de caras de un poliedro, incluida la ecuación de Dehn-Somerville , que, expresada en términos de vectores h de politopos simpliciales, toma la forma simple h k = h d − k para cualquier k _ La variante de estas ecuaciones con k = 0 es equivalente a la fórmula de Euler, pero para d > 3 estas ecuaciones son linealmente independientes entre sí e imponen restricciones adicionales sobre el vector h (y por lo tanto sobre el vector ƒ) [4] .

Otra desigualdad importante para el número de caras de un politopo proviene del teorema del límite superior demostrado por primera vez por McMullen [6] , que establece que un politopo de dimensión d con n vértices no puede tener más caras de ninguna dimensión que un politopo adyacente . politopo con el mismo número de vértices:

donde el asterisco significa que el último término de la suma debe reducirse a la mitad si d es par [7] . Se sigue asintóticamente que no puede haber más que caras de todas las dimensiones.

Incluso para la dimensión cuatro, el conjunto de todos los vectores ƒ posibles de los poliedros convexos no forma un subconjunto convexo de la red de enteros de cuatro dimensiones, y queda mucho por aclarar acerca de los posibles valores de estos vectores [8] .

Propiedades de la teoría de grafos

Junto con el número de caras de los poliedros, los investigadores también estudian sus otras propiedades combinatorias, como las propiedades de los gráficos obtenidos a partir de los vértices y las aristas de los poliedros (su esqueleto de 1 ).

El teorema de Balinsky establece que un gráfico obtenido de esta manera a partir de cualquier poliedro convexo d -dimensional es vértice - d - conexo [9] [10] . En el caso de los 3 politopos, esta propiedad y la planaridad se pueden usar para describir con precisión los gráficos de politopos: el teorema de Steinitz establece que G es el esqueleto de un 3 politopos si y solo si G es un gráfico plano conectado por 3 vértices [11 ] .

El teorema de Blind y Money-Levitsk [12] (enunciado como una conjetura por Micha Perles) establece que es posible reconstruir la estructura de la cara de un politopo simple a partir de su gráfico. 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 el grafo sirve como esqueleto. Esta propiedad contrasta marcadamente con las propiedades de los politopos adyacentes (no simples) cuyos gráficos son completos  : puede haber muchos poliedros adyacentes diferentes con el mismo gráfico. Kalai [13] proporcionó otra prueba de este teorema , y ​​Friedman [14] mostró cómo usar este teorema para crear un algoritmo de tiempo polinomial para construir poliedros simples a partir de sus gráficos.

En el contexto de la programación lineal símplex , es importante considerar el diámetro de un poliedro, el número mínimo de vértices que deben atravesarse para llegar a cualquier vértice desde cualquier otro vértice. El sistema de desigualdades lineales de un problema de programación lineal determina las caras del poliedro de soluciones admisibles al problema, y ​​el método simplex encuentra la solución óptima, pasando por las aristas de este poliedro. Así, el diámetro evalúa el límite inferior del número de pasos de este método. La conjetura de Hirsch refutada dio un fuerte límite superior en el diámetro [15] . Se conoce un límite superior más débil (cuasi-polinomio) para el diámetro [16] , y la conjetura de Hirsch ha sido probada para ciertas clases de poliedros [17] .

Propiedades computacionales

Determinar si el número de vértices de un poliedro dado está acotado por algún número natural k es una tarea difícil y pertenece a la clase de complejidad PP [18] .

Caras de poliedros 0-1

En el contexto de los métodos de corte para la programación de enteros, es importante poder describir con precisión los chaflanes (caras) del poliedro, en los que se encuentran los vértices, correspondientes a las soluciones de problemas de optimización combinatoria. A menudo, estos problemas tienen soluciones que se pueden dar mediante vectores de bits , y los poliedros correspondientes tienen vértices cuyas coordenadas son los números cero y uno.

Como ejemplo, tome el poliedro de Birkhoff , un conjunto de matrices n  ×  n que pueden formarse mediante combinaciones convexas de matrices de permutación . De manera similar, los vértices de este politopo se pueden entender como una descripción de todas las coincidencias perfectas del grafo bipartito completo , y el problema de optimización lineal en este politopo se puede considerar como un problema para encontrar una coincidencia perfecta mínima ponderada. El teorema de Birkhoff establece que tal poliedro se puede describir usando dos tipos de desigualdades lineales. En primer lugar, cada elemento de la matriz es no negativo y, en segundo lugar, para cada columna y para cada fila, la suma de los elementos de la matriz es igual a uno. Las restricciones a la suma sobre filas y columnas definen un subespacio lineal de dimensión n 2  − 2 n  + 1 en el que se encuentra el poliedro de Birkhoff, y las restricciones a la no negatividad de los elementos de la matriz definen las caras del politopo en este subespacio.

El poliedro de Birkhoff es inusual porque se conoce una descripción completa de sus caras. Para muchos otros poliedros 0-1, hay exponencialmente (o superexponencialmente) muchas caras, y solo está disponible una descripción parcial de ellas [19] .

Véase también

Notas

  1. ↑ Ziegler, 1995 , pág. 51.
  2. ↑ Ziegler, 1995 , pág. 245–246.
  3. ↑ Ziegler, 1995 , pág. 272.
  4. ↑ 12 Ziegler , 1995 , pág. 246–253.
  5. ↑ Steinitz, 1906 .
  6. ↑ Mc Mullen, 1970 .
  7. ↑ Ziegler, 1995 , pág. 254–258.
  8. ↑ Höppner, Ziegler, 2000 .
  9. ↑ Balinsky, 1961 .
  10. ↑ Ziegler, 1995 , pág. 95–96.
  11. ↑ Ziegler, 1995 , pág. 103–126.
  12. ↑ Ciego, Mani-Levitska, 1987 .
  13. ↑ Kalai, 1988 .
  14. ↑ Friedman, 2009 .
  15. ↑ Santos, 2012 .
  16. ↑ Kalai, Kleitman, 1992 .
  17. ↑ Naddef (1989) .
  18. ↑ Haase y Kiefer 2015 , pág. Thm. 5.
  19. ↑ Ziegler, 2000 .

Literatura

Enlaces