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 en 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 llegar a cualquier vértice desde cualquier otro vértice). Además, muchos informáticos utilizan la frase "combinatoria poliédrica" para describir la investigación de 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 de números enteros .
Caras y vectores de conteo de caras
Una cara de un politopo convexo P se puede definir como la intersección de P y un semiespacio cerrado H de tal manera 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 este casco. Las caras de dimensión 0 son los vértices en sí, y las caras de una dimensión (llamadas aristas ) son segmentos de línea que conectan pares de vértices. Tenga en cuenta que esta definición también incluye como caras el conjunto vacío y el politopo P completo . Si el propio P tiene dimensión d , las caras de P con dimensión d - 1 se denominan facetas de P y las caras con dimensión d - 2 se denominan crestas . [1] Las caras de P pueden estar parcialmente ordenadas por inclusión, formando una celosía de caras que tiene como elemento superior el propio P y como elemento inferior el 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 f es (8,12,6). El politopo dual tiene un vector f con los mismos números en orden inverso; así, por ejemplo, el octaedro regular , el dual de un cubo, tiene el vector f (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 = 1 cuenta el conjunto vacío como una cara, mientras que en el lado derecho, f d = 1 cuenta el propio P. 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 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 los politopos simpliciales (politopos en los que cada faceta es un simplex ), 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 vector h enumera los coeficientes del polinomio h ( x ) = ƒ ( x - 1) (nuevamente, para el 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 una forma mucho más conveniente y concisa de codificar la información sobre los números de caras que los vectores ƒ".
Igualdades y desigualdades
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 varían sobre los coeficientes del vector ƒ extendido. En tres dimensiones, mover los dos unos 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. desde el hecho de que cada faceta de un poliedro tridimensional tiene al menos tres bordes, se sigue por doble conteo que 2 e ≥ 3 f , y el uso de esta desigualdad para eliminar e y f de la fórmula cables de Euler para la otras desigualdades e ≤ 3 v - 6 yf ≤ 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 f 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 vectores h (y por lo tanto también los vectores ƒ) de formas adicionales. [4]
Otra desigualdad importante en el recuento de caras de politopos viene dada por el teorema del límite superior , probado 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:
donde el asterisco significa que el término final de la suma debe dividirse 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 del retículo de enteros de cuatro dimensiones, y aún se desconoce mucho acerca de los posibles valores de estos vectores. [7]
Propiedades de la teoría de grafos
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-esqueleta ).
El teorema de Balinski establece que el gráfico obtenido de esta manera a partir de cualquier politopo convexo d -dimensional está conectado al vértice d . [8] En el caso de poliedros tridimensionales, esta propiedad y planaridad pueden usarse para caracterizar exactamente las gráficas de poliedros: el teorema de Steinitz establece que G es el esqueleto de un poliedro tridimensional si y solo si G es un poliedro de 3 dimensiones. grafo plano conectado a vértices. [9]
Un teorema de Blind y Mani-Levitska (1987) (previamente conjeturado por Micha Perles ) establece que uno puede reconstruir la estructura de la cara de un politopo simple a partir de su gráfico. Es decir, si un gráfico 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 gráfico es un gráfico completo ; puede haber muchos politopos vecinos diferentes para el mismo gráfico. Kalai (1988) dio otra prueba de este teorema basada en orientaciones de sumidero únicas , 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 gráficos. Sin embargo, probar si un gráfico o celosía dado se puede realizar como el entramado de caras de un politopo simple es equivalente (por polaridad) a la realización de politopos simpliciales , que se demostró que es completa para la teoría existencial de los reales por Adiprasito y Padrol ( 2014) .
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 por una ruta desde cualquier otro vértice. El sistema de desigualdades lineales de un programa lineal define las facetas de un politopo que representan todas las soluciones factibles del programa, y el método simplex encuentra la solución óptima siguiendo una ruta en este politopo. Por tanto, el diámetro proporciona un límite inferior al número de pasos que requiere este método. La conjetura de Hirsch , ahora refutada, sugirió un fuerte límite sobre cuán grande podría ser el diámetro. [10] Se conocen límites superiores más débiles (cuasi-polinomiales) del diámetro, [11] así como pruebas de la conjetura de Hirsch para clases especiales de politopos. [12]
Propiedades computacionales
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]
Facetas de politopos 0-1
Es importante en el contexto de los métodos de plano de corte para la programación de enteros poder describir con precisión las facetas de los politopos que tienen vértices correspondientes 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 que son todas cero o uno.
Como ejemplo, considere el politopo de Birkhoff , el conjunto de n × n matrices que se pueden formar a partir de combinaciones convexas de matrices de permutación . De manera equivalente, se puede pensar que sus vértices describen todas las coincidencias perfectas en un gráfico bipartito completo , y un problema de optimización lineal en este politopo se puede interpretar como un problema de coincidencia perfecta 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, hay una restricción de que esta celda tiene un valor no negativo. Y en segundo lugar, para cada fila o columna de la matriz, existe la restricción de que la suma de las celdas de esa fila o columna sea igual a una. 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 las 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]
Ver también
- Politopo abstracto
- Álgebra conmutativa combinatoria
- Politopo matroide
- Solicitar politopo
- Esfera simple
- Politopo a juego estable
Notas
- ^ Ziegler (1995) , p. 51.
- ^ Ziegler (1995) , págs. 245–246.
- ^ Ziegler (1995) , p. 272.
- ↑ a b Ziegler (1995) , págs. 246-253.
- ^ Steinitz (1906) .
- ^ Ziegler (1995) , págs. 254-258.
- ^ Höppner y Ziegler (2000) .
- ^ Balinski (1961) ; Ziegler (1995) , págs. 95–96.
- ^ Ziegler (1995) , págs. 103-126.
- ↑ Santos (2011) .
- ^ Kalai y Kleitman (1992) .
- ^ Naddef (1989) .
- ^ Haase y Kiefer (2016) , Thm. 5.
- ^ Ziegler (2000) .
Referencias
- Adiprasito, Karim A .; Padrol, Arnau (2014), El teorema de universalidad para politopos vecinos , arXiv : 1402.7207 , Bibcode : 2014arXiv1402.7207A.
- Balinski, Michel L. (1961), "Sobre la estructura gráfica de poliedros convexos en el espacio n", Pacific Journal of Mathematics , 11 : 431–434, doi : 10.2140 / pjm.1961.11.431.
- Ciego, Roswitha; Mani-Levitska, Peter (1987), "Rompecabezas e isomorfismos de politopos", Aequationes Mathematicae , 34 (2–3): 287–297, doi : 10.1007 / BF01830678 , MR 0921106.
- Cook, William; Seymour, Paul D. (1989), Combinatoria poliédrica , Serie DIMACS en Matemáticas Discretas y Ciencias de la Computación Teórica, Sociedad Matemática Estadounidense , ISBN 978-0-8218-6591-0.
- Friedman, Eric J. (2009), "Encontrar un politopo simple a partir de su gráfica en tiempo polinomial", Geometría discreta y computacional , 41 (2): 249-256, doi : 10.1007 / s00454-008-9121-7 , MR 2471873.
- Haase, Christoph; Kiefer, Stefan (2016), "La complejidad del K- ésimo problema del subconjunto más grande y problemas relacionados", Information Processing Letters , 116 (2): 111-115, arXiv : 1501.06729 , doi : 10.1016 / j.ipl.2015.09.015
- Höppner, Andrea; Ziegler, Günter M. (2000), Un censo de vectores bandera de 4 politopos. En Kalai y Ziegler (2000) , págs. 105-110.
- Kalai, Gil (1988), "Una manera simple de distinguir un politopo simple de su gráfico", Journal of Combinatorial Theory , Serie A, 49 (2): 381–383, doi : 10.1016 / 0097-3165 (88) 90064- 7 , MR 0964396.
- Kalai, Gil ; Kleitman, Daniel J. (1992), "Un cuasi-polinomio ligado para el diámetro de las gráficas de poliedros", Boletín de la American Mathematical Society , 26 (2): 315–316, arXiv : math / 9204233 , doi : 10.1090 / S0273-0979-1992-00285-9 , MR 1130448.
- Kalai, Gil ; Ziegler, Günter M. (2000), Politopos: Combinatoria y Computación , Seminario DMV, 29 , Birkhäuser, ISBN 978-3-7643-6351-2.
- McMullen, Peter (1970), "El número máximo de caras de un politopo convexo", Mathematika , 17 : 179-184, doi : 10.1112 / S0025579300002850.
- Naddef, Denis (1989), "La conjetura de Hirsch es cierta para (0,1) -politopos", Programación matemática , 45 (1): 109-110, doi : 10.1007 / BF01589099 , MR 1017214.
- Santos, Francisco (2011), "Un contraejemplo de la conjetura de Hirsch", Annals of Mathematics , Princeton University and Institute for Advanced Study, 176 (1): 383–412, arXiv : 1006.2814 , doi : 10.4007 / annals.2012.176.1.7 , MR 2925387
- Schrijver, Alexander (1987), Combinatoria poliédrica , Centrum voor Wiskunde en Informatica.
- Steinitz, Ernst (1906), "Über die Eulerschen Polyederrelationen", Archiv für Mathematik und Physik , 11 : 86–88.
- Ziegler, Günter M. (1995), Conferencias sobre politopos , Textos de posgrado en matemáticas, 152 , Springer-Verlag, ISBN 0-387-94365-X.
- Ziegler, Günter M. (2000), Conferencias sobre politopos 0-1. En Kalai y Ziegler (2000) .
enlaces externos
- Kalai, Gil (2008), Cinco problemas abiertos sobre politopos convexos.