politopo integral

En geometría y combinatoria poliédrica , un politopo integral es un politopo convexo cuyos vértices tienen coordenadas cartesianas enteras . ^{[ 1 ]} Es decir, es un politopo que es igual a la envoltura convexa de sus puntos enteros . ^{[ 2 ]} Los politopos integrales también se denominan politopos reticulares o politopos Z (por el conjunto Z ). Los casos especiales de politopos integrales bidimensionales y tridimensionales se denominan polígonos integrales o poliedros integrales , respectivamente.

Un${\displaystyle n}$Un simplex regular de dimensión -dimensional puede representarse como un politopo entero en${\displaystyle \mathbb {R} ^{n+1}}$, la envoltura convexa de los puntos enteros para los cuales una coordenada es uno y el resto son cero. Otro tipo importante de simplex integral, el ortoesquema , puede formarse como la envoltura convexa de puntos enteros cuyas coordenadas comienzan con una cierta cantidad de unos consecutivos seguidos de ceros en todas las coordenadas restantes.${\displaystyle n}$-cubo unitario dimensional en${\displaystyle \mathbb {R} ^{n}}$Un permutaedro tiene como vértices todos los puntos enteros cuyas coordenadas son cero o uno. Un permutaedro tiene vértices cuyas coordenadas se obtienen aplicando todas las permutaciones posibles al vector.${\displaystyle (1,2,...,n)}$. Un asociaedro en la realización convexa de Loday es también un politopo entero y una deformación del permutaedro.

En el contexto de la programación lineal y problemas relacionados de optimización matemática , los politopos convexos suelen describirse mediante un sistema de desigualdades lineales que deben cumplir sus puntos. Cuando un politopo es entero, la programación lineal puede utilizarse para resolver problemas de programación entera para el sistema de desigualdades dado, un problema que de otro modo sería más difícil.

Algunos poliedros que surgen de problemas de optimización combinatoria son automáticamente enteros. Por ejemplo, esto es cierto para el politopo de orden de cualquier conjunto parcialmente ordenado , un politopo definido por desigualdades por pares entre coordenadas correspondientes a elementos comparables en el conjunto. ^{[ 3 ]} Otro politopo bien conocido en optimización combinatoria es el politopo de emparejamiento . Claramente, se busca encontrar emparejamientos algorítmicamente y una técnica es la programación lineal. El politopo descrito por el programa lineal que acota superiormente la suma de aristas tomadas por vértice es entero en el caso de grafos bipartitos , es decir, describe exactamente el politopo de emparejamiento, mientras que para grafos generales no es entero. ^{[ 4 ]} Por lo tanto, para grafos bipartitos, basta con resolver el programa lineal correspondiente para obtener un emparejamiento válido . Sin embargo, para grafos generales, hay otras dos caracterizaciones del politopo de emparejamiento, una de las cuales utiliza la desigualdad de Blossom para subconjuntos impares de vértices y, por lo tanto, permite relajar el programa entero a un programa lineal y aun así obtener emparejamientos válidos. ^{[ 5 ]} Estas caracterizaciones son de mayor interés en el famoso algoritmo de floración de Edmonds, utilizado para encontrar tales emparejamientos en grafos generales.

Para un politopo descrito por desigualdades lineales, cuando el politopo no es entero, se puede demostrar su no integralidad encontrando un vértice cuyas coordenadas no sean enteras. Dicho vértice se puede describir combinatoriamente especificando un subconjunto de desigualdades que, al transformarse en un sistema de ecuaciones lineales , tienen una solución única, y verificando que este punto de solución satisface todas las demás desigualdades. Por lo tanto, la comprobación de la integralidad pertenece a la clase de complejidad coNP de problemas para los que se puede demostrar fácilmente una respuesta negativa. Más específicamente, es coNP-completa . ^{[ 6 ]}

Muchas de las propiedades importantes de un politopo integral, incluyendo su volumen y número de vértices, están codificadas por su polinomio de Ehrhart . ^{[ 7 ]}

Los politopos integrales tienen un papel destacado en la teoría de las variedades tóricas , donde corresponden a variedades tóricas proyectivas polarizadas. Por ejemplo, la variedad tórica correspondiente a un simplex es un espacio proyectivo . La variedad tórica correspondiente a un cubo unitario es la incrustación de Segre del${\displaystyle n}$-producto plegado de la línea proyectiva.

En geometría algebraica , un ejemplo importante de politopos reticulares llamados politopos de Newton son las envolturas convexas de vectores que representan los exponentes de cada variable en los términos de un polinomio . Por ejemplo, el polinomio${\displaystyle xy+2x^{2}+y^{5}+4}$tiene cuatro términos,${\displaystyle xy}$con vector exponencial (1,1),${\displaystyle 2x^{2}}$con vector exponencial (2,0),${\displaystyle y^{5}}$con vector exponencial (0,5), y${\displaystyle 4}$con vector exponencial (0,0). Su politopo de Newton es la envoltura convexa de los cuatro puntos (1,1), (2,0), (0,5) y (0,0). Esta envoltura es un triángulo entero con el punto (1,1) en su interior y los otros tres puntos como vértices.

• politopo de Delzant
• tetraedro de Reeve