Grafo de un politopo

El grafo de aristas de un politopo convexo es un grafo simple finito. Está conectado, ya que se puede obtener un camino entre dos vértices cualesquiera a partir del algoritmo símplex. Para politopos de baja dimensión, la estructura del grafo de aristas está esencialmente determinada por la dimensión del politopo:

• El único politopo de dimensión 0 es el punto; su grafo de aristas es ${\displaystyle K_{1}}$.
• El único politopo de dimensión 1 es el segmento de recta; su grafo de aristas es ${\displaystyle K_{2}}$.
• Los politopos de dimensión 2 son polígonos. El grafo de aristas de un polígono de ${\displaystyle n}$ lados es ${\displaystyle C_{n}}$, un ciclo con ${\displaystyle n}$ vértices.
• Los grafos de aristas de politopos de dimensión 3 son ricos en estructura, pero han sido intensamente estudiados: según el teorema de Steinitz, los grafos de aristas de politopos de dimensión 3 son precisamente los grafos planos 3-vértices conectados, por lo que también se les conoce como grafos poliédricos.

Para los politopos ${\displaystyle d}$ con ${\displaystyle d\geq 4}$, no se conoce ninguna caracterización de los grafos de aristas.

Se pueden hacer algunas afirmaciones generales:

• El grafo de aristas tiene un grado mínimo de al menos ${\displaystyle d}$. Si cada vértice de un politopo ${\displaystyle d}$ tiene exactamente grado ${\displaystyle d}$ (es decir, el grafo de aristas es ${\displaystyle d}$-regular), entonces se dice que el politopo es simple.

• El grafo de aristas es ${\displaystyle d}$-vértices conectado, condición establecida según el teorema de Balinski.

• El grafo de aristas contiene una subdivisión del grafo completo ${\displaystyle K_{d+1}}$.^[1] En particular, para ${\displaystyle d\geq 4}$, el grafo de aristas contiene un ${\displaystyle K_{5}}$-menor, y no es plano.

En general, no es trivial determinar si un grafo dado es el grafo de aristas de un politopo, es decir, si es un grafo politópico. Para algunas clases de grafos, como los grafos de grado mínimo ${\displaystyle \delta \leq 3}$, las propiedades anteriores pueden ayudar a resolver esta cuestión. Por ejemplo, el grafo de Petersen es 3-regular. Por lo tanto, si fuera politópico, sería el grafo de aristas de un politopo tridimensional. Sin embargo, el grafo de Petersen no es planar y, por lo tanto, no puede ser el grafo de aristas de un 3-politopo.

Para grafos de grado mínimo ${\displaystyle \delta \geq 4}$, estas preguntas suelen ser mucho más difíciles de responder. Por ejemplo, a julio de 2025 se desconocía si el producto cartesiano de dos grafos de Petersen es politópico.^[2] Se sabe que si fuera politópico, entonces el politopo debe ser de dimensión cuatro o cinco.^[3]

• El grafo ciclo ${\displaystyle C_{n}}$ es el grafo de aristas de un polígono de ${\displaystyle n}$ lados.
• El grafo completo ${\displaystyle K_{n}}$ es el grafo de aristas del símplex de dimensiones ${\displaystyle (n-1)}$ (incluyendo el triángulo, el tetraedro y el pentácoron).
• El grafo hipercubo ${\displaystyle Q_{n}}$ es el grafo de aristas del hipercubo ${\displaystyle n}$-dimensional (incluyendo el cuadrado y el cubo). Su grafo de dos-distancia se conoce como el grafo de medio cubo y es el grafo de aristas del demihipercubo correspondiente.
• El grafo de Turán ${\displaystyle T(2n,n)}$ (también conocido como grafo del cóctel^[4]) es el grafo de aristas del politopo de cruce ${\displaystyle n}$-dimensional (incluyendo al octaedro y al hexadecacoron).
• El grafo de Johnson ${\displaystyle J(n,k)}$ es el grafo de aristas del hipersímplex ${\displaystyle \Delta _{n,k}}$.
• El grafo de Hamming ${\displaystyle H(d,q)}$ es el grafo de aristas de la ${\displaystyle d}$-ésima potencia cartesiana del símplex ${\displaystyle (q-1)}$-dimensional. Esto incluye los grafos de aristas tanto de símplices ${\displaystyle H(1,q)}$ como de hipercubos ${\displaystyle H(d,2)}$, pero también de otros politopos como el (3,3)-duoprisma ${\displaystyle H(2,3)}$.
• El grafo de Bruhat es el grafo de aristas del permutaedro. En términos más generales, el grafo de Cayley de un grupo de Coxeter finito (con los generadores naturales) es el grafo de aristas del politopo uniforme omnitruncado correspondiente, o, más generalmente, el grafo de aristas de un politopo orbital genérico del grupo de reflexiones asociado.

• El grafo icosaédrico es el grafo de aristas del icosaedro regular.
• El grafo dodecaédrico es el grafo de aristas del dodecaedro regular.
• El grafo de Schläfli es el grafo de aristas del 2₂₁ politopo de 6 dimensiones.
• El grafo de Gosset es el grafo de aristas del 3₂₁ politopo de 7 dimensiones.

Algunas operaciones sobre politopos se traducen de forma natural a sus grafos de aristas.

• El grafo de aristas del producto cartesiano ${\displaystyle P\times Q}$ de dos politopos es el grafo producto cartesiano de los grafos de aristas de ${\displaystyle P}$ y ${\displaystyle Q}$. Por ejemplo, el producto de un grafo cíclico y ${\displaystyle K_{1}}$ es el grafo de aristas de un prisma. Existen grafos no politópicos cuyo producto es politópico.^[3]
• El grafo de aristas de la unión ${\displaystyle P\star Q}$ de dos politopos es la unión de grafos de los grafos de aristas de ${\displaystyle P}$ y de ${\displaystyle Q}$. La unión de grafos se construye a partir de la unión disjunta de los grafos de aristas sumando todas las aristas entre ellos. Se obtiene el mismo grafo de aristas para la suma directa de ${\displaystyle P\oplus Q}$ (el dual del producto cartesiano) bajo el supuesto de que tanto ${\displaystyle P}$ como ${\displaystyle Q}$ tienen dimensión al menos dos.
• Para politopos tridimensionales, el grafo de aristas de un poliedro dual es el grafo dual del grafo de aristas del poliedro original.

Summarize Timeline Fact Check

Dado el grafo de aristas de un politopo de dimensión tres o inferior, es posible reconstruir la combinatoria completa del politopo, es decir, la lista completa de caras e incidencias entre ellas.

Por ejemplo, las caras bidimensionales de un politopo de dimensión 3 corresponden exactamente a los ciclos inducidos no separables en el grafo de aristas.^[5]

Además, para politopos de dimensión hasta tres, es posible determinar la dimensión del politopo a partir del grafo de aristas. En la dimensión ${\displaystyle d\geq 4}$, esto no es posible. Existen politopos combinatoriamente distintos con grafos de aristas isomorfos, e incluso politopos de diferentes dimensiones con grafos de aristas isomorfos.

El grafo de aristas de un símplex es un grafo completo. Sin embargo, en la dimensión ${\displaystyle d\geq 4}$ existen otros politopos cuyo grafo de aristas es completo, que se denominan 1-politopos vecinos. Por ejemplo, tanto el simplex de dimensión ${\displaystyle d}$ como el politopo de 4 dimensiones politopo cíclico ${\displaystyle C_{4}(d+1)}$ tienen un grafo de aristas ${\displaystyle K_{d+1}}$.

Los hipercubos de dimensión suficientemente grande comparten sus grafos de aristas con los politopos cúbicos vecinos. Por ejemplo, el grafo de aristas del hipercubo de 10 dimensiones es también el grafo de aristas de un politopo de 4 dimensiones.^[6]

Una técnica general para obtener politopos combinatoriamente distintos con el mismo grafo de aristas consiste en construir tanto la suma directa como la unión de dos politopos. Si bien estas operaciones nunca generan politopos de la misma dimensión, los politopos resultantes siempre tienen el mismo grafo de aristas (suponiendo que se parte de politopos de dimensión al menos dos). Por ejemplo, la unión ${\displaystyle \Delta \star \Delta }$ de dos triángulos es un simplex de 5 dimensiones, mientras que la suma directa ${\displaystyle \Delta \oplus \Delta }$ es el politopo cíclico de cuatro dimensiones con seis vértices ${\displaystyle C_{4}(6)}$. Ambos tienen como grafo de aristas ${\displaystyle K_{6}}$.

La reconstrucción de la combinatoria completa a partir del grafo de aristas es posible en casos especiales o cuando se dispone de datos adicionales:

• La combinatoria de un politopo simple puede reconstruirse a partir del grafo de aristas. Esto fue demostrado por primera vez por Blind y Mani.^[7] Posteriormente, Gil Kalai proporcionó una demostración breve utilizando la orientación de sumidero única.^[8]
• La combinatoria de un zonotopo puede reconstruirse a partir del grafo de aristas.^[9][10]
• Para politopos simpliciales, dados el grafo de aristas del politopo y su espacio de autotensiones, es posible reconstruir el politopo hasta la equivalencia afín.^[11]