Hispanopedia Wiki
Articulo de referencia

Teorema de Steinitz

En combinatoria poliédrica , una rama de las matemáticas, el teorema de Steinitz caracteriza los grafos no dirigidos formados por las aristas y los vértices de poliedros convexo...

Hispanopedia WikiContenido en espanolLectura gratuita
Este es un buen artículo. Haz clic aquí para obtener más información.

En combinatoria poliédrica , una rama de las matemáticas, el teorema de Steinitz caracteriza los grafos no dirigidos formados por las aristas y los vértices de poliedros convexos tridimensionales : son precisamente los grafos planares 3-conexos . Es decir, todo poliedro convexo forma un grafo planar 3-conexo, y todo grafo planar 3-conexo puede representarse como el grafo de un poliedro convexo. Por esta razón, los grafos planares 3-conexos también se conocen como grafos poliédricos . [ 1 ]

Este resultado proporciona un teorema de clasificación para los poliedros convexos tridimensionales, algo desconocido en dimensiones superiores. [ 2 ] Proporciona una descripción completa y puramente combinatoria de los grafos de vértices y aristas de estos poliedros, lo que permite demostrar más fácilmente otros resultados sobre ellos, como el teorema de Eberhard sobre la realización de poliedros con tipos de caras dados, sin referencia a la geometría de estas formas. [ 3 ] Además, se ha aplicado en el dibujo de grafos , como una forma de construir visualizaciones tridimensionales de grafos abstractos. [ 4 ] Branko Grünbaum ha llamado a este teorema "el resultado conocido más importante y profundo sobre 3-politopos ". [ 5 ]

El teorema aparece en una publicación de 1922 de Ernst Steinitz , [ 6 ] de quien recibe su nombre. Puede demostrarse por inducción matemática (como hizo Steinitz), hallando el estado de energía mínima de un sistema de resortes bidimensional y extendiendo el resultado a tres dimensiones, o utilizando el teorema de empaquetamiento de círculos . Se conocen varias extensiones del teorema, en las que el poliedro que realiza un grafo dado tiene restricciones adicionales; por ejemplo, todo grafo poliédrico es el grafo de un poliedro convexo con coordenadas enteras, o el grafo de un poliedro convexo cuyas aristas son tangentes a una esfera media común .

Definiciones y enunciado del teorema

Al iluminar el esqueleto de un poliedro convexo con una fuente de luz cercana a una de sus caras, sus sombras forman un diagrama de Schlegel plano .

Un grafo no dirigido es un sistema de vértices y aristas , donde cada arista conecta dos de los vértices. Como es común en la teoría de grafos, para los fines del teorema de Steinitz, estos grafos se restringen a ser finitos (los vértices y las aristas son conjuntos finitos ) y simples (ninguna arista conecta los mismos dos vértices, ni conecta un vértice consigo mismo). A partir de cualquier poliedro se puede formar un grafo, haciendo que los vértices del grafo se correspondan con los vértices del poliedro y conectando dos vértices cualesquiera del grafo mediante una arista siempre que los dos vértices correspondientes del poliedro sean los extremos de una arista del poliedro. Este grafo se conoce como el esqueleto del poliedro. [ 7 ]

Un grafo es planar si puede dibujarse con sus vértices como puntos en el plano euclidiano y sus aristas como curvas que conectan estos puntos, de manera que no se crucen dos curvas de arista y que el punto que representa un vértice se encuentre sobre la curva que representa una arista solo cuando el vértice sea un extremo de la arista. Según el teorema de Fáry , todo dibujo planar puede enderezarse de modo que las curvas que representan las aristas sean segmentos de línea . Un grafo es 3-conexo si tiene más de tres vértices y, tras la eliminación de dos cualesquiera de sus vértices, cualquier otro par de vértices permanece conectado por un camino. El teorema de Steinitz establece que estas dos condiciones son necesarias y suficientes para caracterizar los esqueletos de poliedros convexos tridimensionales: un grafo dadoGRAMO{\displaystyle G}es la gráfica de un poliedro tridimensional convexo, si y solo siGRAMO{\displaystyle G}es planar y 3-conexo por vértices. [ 5 ] [ 8 ]

Pruebas

Ilustración de la demostración del teorema de Balinski , que muestra el conjunto cero de una función lineal (azul) que pasa por dos vértices dados (amarillo) y los caminos del método simplex que conectan el grafo restante (verde).

Una de las direcciones del teorema de Steinitz (la más fácil de demostrar) establece que la gráfica de todo poliedro convexo es planar y 3-conexa. Como se muestra en la ilustración, la planaridad se puede demostrar utilizando un diagrama de Schlegel : si se coloca una fuente de luz cerca de una cara del poliedro y un plano en el otro lado, las sombras de las aristas del poliedro formarán una gráfica planar, incrustada de tal manera que las aristas son segmentos de línea recta. La 3-conectividad de una gráfica poliédrica es un caso especial del teorema de Balinski que establece que la gráfica de cualquierk{\displaystyle k}politopo convexo de dimensión -k{\displaystyle k}-conectado. La conectividad del grafo de un politopo, después de eliminar cualquierk−1{\displaystyle k-1}de sus vértices, se puede demostrar eligiendo un vértice másv{\displaystyle v}, encontrar una función lineal que sea cero en el conjunto resultante dek{\displaystyle k}vértices, y siguiendo las rutas generadas por el método simplex para conectar cada vértice a uno de los dos vértices extremos de la función lineal, con el vértice elegidov{\displaystyle v}conectado a ambos. [ 9 ]

La otra vertiente, más compleja, del teorema de Steinitz afirma que todo grafo planar 3-conexo es el grafo de un poliedro convexo. Existen tres enfoques estándar para esta parte: demostraciones por inducción, la elevación de incrustaciones de Tutte bidimensionales a tres dimensiones mediante la correspondencia de Maxwell-Cremona y métodos que utilizan el teorema de empaquetamiento de círculos para generar un poliedro canónico .

Inducción

Transformación ΔY y YΔ de un poliedro

Aunque la demostración original de Steinitz no se expresó en términos de teoría de grafos, puede reescribirse en esos términos, e implica encontrar una secuencia de transformaciones ΔY y YΔ que reducen cualquier grafo planar 3-conexo aK4{\displaystyle K_{4}}, el gráfico del tetraedro. Una transformación YΔ elimina un vértice de grado tres de un gráfico, añadiendo aristas entre todos sus antiguos vecinos si esas aristas no existían previamente; la transformación inversa, una transformación ΔY, elimina las aristas de un triángulo de un gráfico y las reemplaza por un nuevo vértice de grado tres adyacente a los mismos tres vértices. Una vez que se encuentra dicha secuencia, se puede invertir y convertir en operaciones geométricas que construyen el poliedro deseado paso a paso a partir de un tetraedro. Cada transformación YΔ en la secuencia inversa se puede realizar geométricamente cortando un vértice de grado tres de un poliedro. Una transformación ΔY en la secuencia inversa se puede realizar geométricamente eliminando una cara triangular de un poliedro y extendiendo sus caras vecinas hasta el punto donde se encuentran, pero solo cuando ese punto de triple intersección de las tres caras vecinas está en el lado opuesto de la cara eliminada del poliedro. Cuando el punto de triple intersección no está en el lado opuesto de esta cara, una transformación proyectiva del poliedro es suficiente para moverlo al lado correcto. Por lo tanto, por inducción sobre el número de transformaciones ΔY y YΔ necesarias para reducir un gráfico dado aK4{\displaystyle K_{4}}, todo grafo poliédrico puede realizarse como un poliedro. [ 5 ]

Un trabajo posterior de Epifanov reforzó la prueba de Steinitz de que todo grafo poliédrico puede reducirse aK4{\displaystyle K_{4}}mediante transformaciones ΔY y YΔ. Epifanov demostró que si se especifican dos vértices en un grafo planar, entonces el grafo puede reducirse a una sola arista entre esos terminales combinando transformaciones ΔY y YΔ con reducciones en serie-paralelo . [ 10 ] La demostración de Epifanov fue complicada y no constructiva, pero Truemper la simplificó utilizando métodos basados ​​en menores de grafos . Truemper observó que todo grafo de cuadrícula es reducible mediante transformaciones ΔY y YΔ de esta manera, que esta reducibilidad se conserva mediante menores de grafos, y que todo grafo planar es un menor de un grafo de cuadrícula. [ 11 ] Esta idea puede usarse para reemplazar el lema de Steinitz de que existe una secuencia de reducción. Después de este reemplazo, el resto de la demostración puede llevarse a cabo usando inducción de la misma manera que la demostración original de Steinitz. [ 8 ] Para estas demostraciones, realizadas utilizando cualquiera de las formas de encontrar secuencias de transformaciones ΔY y YΔ, existen grafos poliédricos que requieren un número no lineal de pasos. Más precisamente, todo grafo planar puede reducirse utilizando un número de pasos como máximo proporcional anorte3/2{\displaystyle n^{3/2}}y un número infinito de gráficos requiere una cantidad de pasos al menos proporcional anorte3/2{\displaystyle n^{3/2}}, dóndenorte{\displaystyle n}es el número de vértices en el grafo. [ 12 ] [ 13 ]

Una forma alternativa de prueba por inducción se basa en eliminar aristas (y comprimir los vértices de grado dos que podrían quedar después de esta eliminación) o contraer aristas y formar un menor del grafo planar dado. Cualquier grafo poliédrico se puede reducir aK4{\displaystyle K_{4}}mediante un número lineal de estas operaciones, y nuevamente las operaciones pueden invertirse y las operaciones invertidas realizarse geométricamente, dando una realización poliédrica del grafo. Sin embargo, si bien es más sencillo demostrar que existe una secuencia de reducción para este tipo de argumento, y las secuencias de reducción son más cortas, los pasos geométricos necesarios para invertir la secuencia son más complicados. [ 14 ]

Levantamiento

Tensión de equilibrio en la gráfica de un cubo
Un tronco de pirámide que eleva el dibujo sometido a tensión (con las mismas posiciones 2D) a 3D.

Si se dibuja un gráfico en el plano con aristas rectas, entonces una tensión de equilibrio se define como la asignación de números reales distintos de cero (pesos) a las aristas, con la propiedad de que cada vértice se encuentra en la posición dada por el promedio ponderado de sus vecinos. Según la correspondencia de Maxwell-Cremona , una tensión de equilibrio puede extenderse a una superficie tridimensional continua lineal por partes, de modo que las aristas que forman los límites entre las partes planas de la superficie se proyectan sobre el dibujo dado. El peso y la longitud de cada arista determinan la diferencia de pendientes de la superficie a ambos lados de la arista, y la condición de que cada vértice esté en equilibrio con sus vecinos es equivalente a la condición de que estas diferencias de pendiente hagan que la superficie se encuentre consigo misma correctamente en la vecindad del vértice. Los pesos positivos se traducen en ángulos diedros convexos entre dos caras de la superficie lineal por partes, y los pesos negativos se traducen en ángulos diedros cóncavos. A la inversa, toda superficie continua lineal por partes se deriva de una tensión de equilibrio de esta manera. Si se dibuja un grafo planar finito y se le aplica una tensión de equilibrio de tal manera que todas las aristas interiores del dibujo tengan pesos positivos y todas las aristas exteriores tengan pesos negativos, entonces, al trasladar esta tensión a una superficie tridimensional de esta forma y luego reemplazar la superficie plana que representa el exterior del grafo por su complemento en el mismo plano, se obtiene un poliedro convexo, con la propiedad adicional de que su proyección perpendicular sobre el plano no tiene intersecciones. [ 15 ] [ 16 ]

La correspondencia de Maxwell-Cremona se ha utilizado para obtener realizaciones poliédricas de grafos poliédricos combinándola con un método de dibujo de grafos planares de WT Tutte , la incrustación de Tutte . El método de Tutte comienza fijando una cara de un grafo poliédrico en una posición convexa en el plano. Esta cara se convertirá en la cara exterior de un dibujo del grafo. El método continúa estableciendo un sistema de ecuaciones lineales en las coordenadas de los vértices, según el cual cada vértice restante debe colocarse en el promedio de sus vecinos. Entonces, como demostró Tutte, este sistema de ecuaciones tendrá una solución única en la que cada cara del grafo se dibuja como un polígono convexo. [ 17 ] Intuitivamente, esta solución describe el patrón que se obtendría reemplazando las aristas interiores del grafo por resortes ideales y dejándolas estabilizarse en su estado de energía mínima. [ 18 ] El resultado es casi una tensión de equilibrio: si se asigna un peso de uno a cada arista interior, entonces cada vértice interior del dibujo está en equilibrio. Sin embargo, no siempre es posible asignar números negativos a las aristas exteriores para que también estén en equilibrio. Esta asignación siempre es posible cuando la cara exterior es un triángulo, por lo que este método puede utilizarse para realizar cualquier grafo poliédrico que tenga una cara triangular. Si un grafo poliédrico no contiene una cara triangular, su grafo dual sí contiene un triángulo y también es poliédrico, por lo que se puede realizar el dual de esta manera y luego realizar el grafo original como el poliedro polar de la realización dual. [ 4 ] [ 19 ] Un método alternativo para realizar poliedros utilizando elevaciones evita la dualidad al elegir cualquier cara con como máximo cinco vértices como cara exterior. Todo grafo poliédrico tiene una cara de este tipo, y al elegir la forma fija de esta cara con mayor cuidado, se puede elevar la incrustación de Tutte del resto del grafo. [ 20 ]

Empaquetado circular

Un poliedro formado a partir de un empaquetamiento circular sobre la esfera azul. Cada vértice del poliedro está representado en el empaquetamiento por su círculo horizonte (rojo). Cada cara está representada por el círculo formado por su intersección con la esfera.

Según una variante del teorema de empaquetamiento de círculos , para cada grafo poliédrico, existe un sistema de círculos en el plano o en cualquier esfera, que representan los vértices y las caras del grafo, de manera que:

  • Cada dos vértices adyacentes del gráfico están representados por círculos tangentes ,
  • Cada dos caras adyacentes del gráfico están representadas por un círculo tangente,
  • cada par formado por un vértice y una cara que toca están representados por círculos que se cruzan en ángulo recto , y
  • Todos los demás pares de círculos están separados entre sí. [ 21 ]

El mismo sistema de círculos forma una representación del grafo dual intercambiando los roles de los círculos que representan vértices y los que representan caras. A partir de cualquier representación de este tipo en una esfera, incrustada en el espacio euclidiano tridimensional, se puede formar un poliedro convexo que es combinatoriamente equivalente al grafo dado, como una intersección de semiplanos cuyos límites pasan por los círculos de las caras. Desde cada vértice de este poliedro, el horizonte en la esfera, visto desde ese vértice, es el círculo que lo representa. Esta propiedad del horizonte determina la posición tridimensional de cada vértice, y el poliedro puede definirse equivalentemente como la envoltura convexa de los vértices, posicionados de esta manera. La esfera se convierte en la esfera media de la realización: cada arista del poliedro es tangente a la esfera, en un punto donde dos círculos de vértice tangentes cruzan dos círculos de cara tangentes. [ 22 ]

Realizaciones con propiedades adicionales

Coordenadas enteras

Es posible demostrar una forma más fuerte del teorema de Steinitz, que establece que cualquier grafo poliédrico puede representarse mediante un poliedro convexo cuyas coordenadas son números enteros . [ 23 ] Por ejemplo, la demostración original de Steinitz basada en inducción puede reforzarse de esta manera. Sin embargo, los números enteros resultantes de la construcción de Steinitz son doblemente exponenciales en el número de vértices del grafo poliédrico dado. Escribir números de esta magnitud en notación binaria requeriría un número exponencial de bits. [ 19 ] Geométricamente, esto significa que algunas características del poliedro pueden tener un tamaño doblemente exponencialmente mayor que otras, lo que hace que las representaciones derivadas de este método sean problemáticas para aplicaciones en el dibujo de grafos . [ 4 ]

Investigadores posteriores han encontrado algoritmos de realización basados ​​en elevación que utilizan solo un número lineal de bits por vértice. [ 20 ] [ 24 ] También es posible relajar el requisito de que las coordenadas sean números enteros y asignar coordenadas de tal manera queincógnita{\displaystyle x}-las coordenadas de los vértices son enteros distintos en el rango de 0 a2norte−4{\displaystyle 2n-4}y las otras dos coordenadas son números reales en el intervalo unitario , de modo que cada arista tiene una longitud de al menos uno, mientras que el poliedro en su conjunto tiene un volumen lineal. [ 25 ] [ 26 ] Se sabe que algunos grafos poliédricos son realizables en cuadrículas de tamaño solo polinomial; en particular, esto es cierto para las pirámides (realizaciones de grafos de rueda ), los prismas (realizaciones de grafos de prisma ) y los poliedros apilados (realizaciones de redes apolíneas ). [ 27 ]

Otra forma de enunciar la existencia de realizaciones enteras es que todo poliedro convexo tridimensional tiene un poliedro entero combinatoriamente equivalente. [ 23 ] Por ejemplo, el dodecaedro regular no es en sí mismo un poliedro entero, debido a sus caras pentagonales regulares, pero puede realizarse como un piritoedro entero equivalente . [ 20 ] Esto no siempre es posible en dimensiones superiores, donde existen politopos (como los construidos a partir de la configuración de Perles ) que no tienen un equivalente entero. [ 28 ]

Pendientes iguales

Un grafo de Halin es un caso especial de grafo poliédrico, formado a partir de un árbol incrustado en un plano (sin vértices de grado dos) mediante la conexión de las hojas del árbol en un ciclo . Para los grafos de Halin, se pueden elegir realizaciones poliédricas de un tipo especial: el ciclo exterior forma una cara base convexa horizontal, y todas las demás caras se encuentran directamente encima de la cara base (como en los poliedros realizados mediante elevación), con todas estas caras superiores teniendo la misma pendiente. Se pueden construir superficies poliédricas con caras de igual pendiente sobre cualquier polígono base (no necesariamente convexo) a partir del esqueleto recto del polígono , y una forma equivalente de describir esta realización es que la proyección bidimensional del árbol sobre la cara base forma su esqueleto recto. La demostración de este resultado utiliza la inducción: cualquier árbol con raíz puede reducirse a un árbol más pequeño eliminando las hojas de un nodo interno cuyos hijos son todos hojas; el grafo de Halin formado a partir del árbol más pequeño tiene una realización según la hipótesis de inducción, y es posible modificar esta realización para agregar cualquier número de hijos hoja al nodo del árbol cuyos hijos fueron eliminados. [ 29 ]

Especificar la forma de una cara

En cualquier poliedro que represente un grafo poliédrico dadoGRAMO{\displaystyle G}, los rostros deGRAMO{\displaystyle G}son exactamente los ciclos enGRAMO{\displaystyle G}que no se separanGRAMO{\displaystyle G}en dos componentes: es decir, eliminando un ciclo facial deGRAMO{\displaystyle G}deja el resto deGRAMO{\displaystyle G}como un subgrafo conexo. Dichos ciclos se denominan ciclos periféricos . Por lo tanto, la estructura combinatoria de las caras (pero no sus formas geométricas) está determinada unívocamente por la estructura del grafo. Otro fortalecimiento del teorema de Steinitz, por Barnette y Grünbaum, establece que para cualquier grafo poliédrico, cualquier cara del grafo y cualquier polígono convexo que represente esa cara, es posible encontrar una realización poliédrica de todo el grafo que tenga la forma especificada para la cara designada. Esto está relacionado con un teorema de Tutte, que afirma que cualquier grafo poliédrico puede dibujarse en el plano con todas las caras convexas y cualquier forma especificada para su cara exterior. Sin embargo, los dibujos de grafos planares producidos por el método de Tutte no necesariamente se extienden a poliedros convexos. En cambio, Barnette y Grünbaum demuestran este resultado utilizando un método inductivo. [ 30 ] También es siempre posible, dado un grafo poliédricoGRAMO{\displaystyle G}y un ciclo arbitrariodo{\displaystyle C}enGRAMO{\displaystyle G}, para encontrar una realización para la cualdo{\displaystyle C}forma la silueta de la realización bajo proyección paralela . [ 31 ]

esferas tangentes

La realización de poliedros mediante el teorema del empaquetamiento de círculos proporciona otro fortalecimiento del teorema de Steinitz: todo grafo planar 3-conexo puede representarse como un poliedro convexo de tal manera que todas sus aristas sean tangentes a la misma esfera unitaria , la esfera media del poliedro. [ 22 ] Al realizar una transformación de Möbius cuidadosamente elegida de un empaquetamiento de círculos antes de transformarlo en un poliedro, es posible encontrar una realización poliédrica que realiza todas las simetrías del grafo subyacente, en el sentido de que todo automorfismo de grafo es una simetría de la realización poliédrica. [ 32 ] [ 33 ] De manera más general, siGRAMO{\displaystyle G}es un grafo poliédrico yK{\displaystyle K}es cualquier cuerpo convexo tridimensional liso , es posible encontrar una representación poliédrica deGRAMO{\displaystyle G}en el que todos los bordes son tangentes aK{\displaystyle K}. [ 34 ]

Los métodos de empaquetamiento de círculos también pueden usarse para caracterizar los grafos de poliedros que tienen una circunsfera que pasa por todos sus vértices, o una insfera tangente a todas sus caras. (Los poliedros con una circunsfera también son importantes en geometría hiperbólica como los poliedros ideales ). En ambos casos, la existencia de una esfera es equivalente a la resolubilidad de un sistema de desigualdades lineales sobre variables reales positivas asociadas a cada arista del grafo. En el caso de la insfera, estas variables deben sumar exactamente uno en cada ciclo de cara del grafo, y más de uno en cada ciclo que no sea de cara. De manera similar, para la circunsfera, las variables deben sumar uno en cada vértice, y más de uno en cada corte con dos o más vértices a cada lado del corte. Aunque puede haber exponencialmente muchas desigualdades lineales que satisfacer, una solución (si existe) puede encontrarse en tiempo polinomial usando el método del elipsoide . Los valores de las variables de una solución determinan los ángulos entre pares de círculos en un empaquetamiento de círculos cuyo poliedro correspondiente tiene la relación deseada con su esfera. [ 35 ] [ 36 ]

Los grafos de poliedros tridimensionales no convexos podrían no estar conectados (izquierda), e incluso para poliedros topológicamente esféricos cuyas caras son polígonos simples, estos grafos podrían no estar 3-conectados (derecha). [ 37 ]

En cualquier dimensión superior a tres, el problema algorítmico de Steinitz consiste en determinar si una red dada es la red de caras de un politopo convexo . Es improbable que tenga una complejidad temporal polinomial, ya que es NP-difícil y más fuertemente completo para la teoría existencial de los reales , incluso para politopos de cuatro dimensiones, según el teorema de universalidad de Richter-Gebert. [ 38 ] Aquí, la teoría existencial de los reales es una clase de problemas computacionales que pueden formularse en términos de encontrar variables reales que satisfagan un sistema dado de ecuaciones e inecuaciones polinomiales. Para el problema algorítmico de Steinitz, las variables de dicho problema pueden ser las coordenadas de los vértices de un politopo, y las ecuaciones e inecuaciones pueden usarse para especificar la planitud de cada cara en la red de caras dada y la convexidad de cada ángulo entre caras. La completitud significa que cualquier otro problema de esta clase puede transformarse en una instancia equivalente del problema algorítmico de Steinitz, en tiempo polinomial. La existencia de tal transformación implica que, si el problema algorítmico de Steinitz tiene una solución en tiempo polinomial, entonces también la tiene todo problema en la teoría existencial de los reales y todo problema en NP. [ 39 ] Sin embargo, debido a que un grafo dado puede corresponder a más de una red de caras, es difícil extender este resultado de completitud al problema del reconocimiento de los grafos vértice-arista de 4-politopos. Determinar la complejidad computacional de este problema de reconocimiento de grafos sigue siendo un problema abierto. [ 40 ]

Los investigadores también han encontrado caracterizaciones teóricas de grafos de los grafos de ciertas clases especiales de poliedros no convexos tridimensionales [ 37 ] [ 41 ] y politopos convexos de cuatro dimensiones. [ 40 ] [ 42 ] [ 43 ] Sin embargo, en ambos casos, el problema general sigue sin resolverse. De hecho, incluso el problema de determinar qué grafos completos son los grafos de poliedros no convexos (distintos deK4{\displaystyle K_{4}}para el tetraedro yK7{\displaystyle K_{7}}para el poliedro de Császár ) sigue sin resolverse. [ 44 ]

El teorema de Eberhard caracteriza parcialmente los multiconjuntos de polígonos que pueden combinarse para formar las caras de un poliedro convexo. Se puede demostrar formando un grafo planar 3-conexo con el conjunto dado de caras de polígonos y, a continuación, aplicando el teorema de Steinitz para hallar una realización poliédrica de dicho grafo. [ 3 ]

László Lovász ha demostrado una correspondencia entre las representaciones poliédricas de grafos y las matrices que realizan los invariantes de grafos de Colin de Verdière de los mismos grafos. El invariante de Colin de Verdière es el corango máximo de una matriz de adyacencia ponderada del grafo, bajo algunas condiciones adicionales que son irrelevantes para los grafos poliédricos. Estas son matrices simétricas cuadradas indexadas por los vértices, con el peso del vérticei{\displaystyle i}en el coeficiente diagonalMETROi,i{\displaystyle M_{i,i}}y con el peso del bordei,j{\displaystyle i,j}en los coeficientes fuera de la diagonalMETROi,j{\displaystyle M_{i,j}}yMETROj,i{\displaystyle M_{j,i}}. Cuando los vérticesi{\displaystyle i}yj{\displaystyle j}no son adyacentes, el coeficienteMETROi,j{\displaystyle M_{i,j}}Se requiere que sea cero. Este invariante es como máximo tres si y solo si el grafo es un grafo planar . Como muestra Lovász, cuando el grafo es poliédrico, se puede obtener una representación del mismo como un poliedro hallando una matriz de adyacencia ponderada de corango tres, hallando tres vectores que forman una base para su espacio nulo , utilizando los coeficientes de estos vectores como coordenadas para los vértices de un poliedro y escalando estos vértices adecuadamente. [ 45 ]

Historia

La historia del teorema de Steinitz es descrita por Grünbaum (2007) , [ 46 ] quien señala su primera aparición en forma críptica en una publicación de Ernst Steinitz , escrita originalmente en 1916. [ 6 ] Steinitz proporcionó más detalles en notas de clase posteriores, publicadas después de su muerte en 1928. Aunque los tratamientos modernos del teorema de Steinitz lo presentan como una caracterización de poliedros en teoría de grafos, Steinitz no utilizó el lenguaje de los grafos. [ 46 ] La formulación en teoría de grafos del teorema fue introducida a principios de la década de 1960 por Branko Grünbaum y Theodore Motzkin , y su demostración también se convirtió a la teoría de grafos en el texto de Grünbaum de 1967, Politopos convexos . [ 46 ] El trabajo de Epifanov sobre las transformaciones ΔY y YΔ , que fortaleció la demostración de Steinitz, estuvo motivado por otros problemas además de la caracterización de poliedros. Truemper (1989) reconoce a Grünbaum el haber observado la relevancia de este trabajo para el teorema de Steinitz. [ 11 ]

La correspondencia de Maxwell-Cremona entre diagramas de tensiones y levantamientos poliédricos fue desarrollada en una serie de artículos por James Clerk Maxwell entre 1864 y 1870, basándose en trabajos anteriores de Pierre Varignon , William Rankine y otros, y fue popularizada a finales del siglo XIX por Luigi Cremona . [ 47 ] La observación de que esta correspondencia puede usarse con la inmersión de Tutte para demostrar el teorema de Steinitz proviene de Eades y Garvan (1995) ; [ 4 ] véase también Richter-Gebert (1996) . [ 38 ]

El teorema del empaquetamiento de círculos fue demostrado por Paul Koebe en 1936 [ 48 ] [ 49 ] y (de forma independiente) por EM Andreev en 1970; [ 49 ] [ 50 ] fue popularizado a mediados de la década de 1980 por William Thurston , a quien (a pesar de citar a Koebe y Andreev) a menudo se le atribuye ser uno de sus descubridores. [ 49 ] La versión del teorema de Andreev ya estaba formulada como una caracterización tipo Steinitz para ciertos poliedros en el espacio hiperbólico , [ 50 ] y el uso del empaquetamiento de círculos para realizar poliedros con esferas medias proviene del trabajo de Thurston. [ 51 ] El problema de caracterizar poliedros con esferas inscritas o circunscritas, resuelto finalmente mediante un método basado en realizaciones de empaquetamiento de círculos, se remonta a un trabajo inédito de René Descartes alrededor de 1630 [ 52 ] y a Jakob Steiner en 1832; [ 35 ] [ 53 ] los primeros ejemplos de poliedros que no tienen realización con una esfera circunscrita o inscrita fueron dados por Steinitz en 1928. [ 35 ] [ 54 ]

Referencias

  1. ↑ Weisstein, Eric W. , "Grafo poliédrico" , MathWorld
  2. ↑ Sturmfels, Bernd (1987), "Los complejos de frontera de politopos convexos no pueden caracterizarse localmente", Journal of the London Mathematical Society , Segunda Serie, 35 (2): 314– 326, CiteSeerX 10.1.1.106.3222 , doi : 10.1112/jlms/s2-35.2.314 , MR 0881520  
  3. 1 2 Malkevitch, Joseph, "Técnicas para demostrar teoremas combinatorios sobre 3-politopos" , Estructuras geométricas (apuntes del curso) , City University of New York
  4. 1 2 3 4 Eades, Peter ; Garvan, Patrick (1995), "Dibujo de grafos planares estresados ​​en tres dimensiones", en Brandenburg, Franz-Josef (ed.), Dibujo de grafos, Simposio sobre dibujo de grafos, GD '95, Passau, Alemania, 20-22 de septiembre de 1995, Actas , Lecture Notes in Computer Science , vol. 1027, Springer, pp. 212–223 , doi : 10.1007/BFb0021805 , ISBN   978-3-540-60723-6, MR 1400675 
  5. 1 2 3 Grünbaum, Branko (2003), "13.1 Teorema de Steinitz", Politopos convexos , Textos de Graduado en Matemáticas , vol. 221 (2ª ed.), Springer-Verlag, págs. 235-244 , ISBN    0-387-40409-0
  6. 1 2 Steinitz, Ernst (1922), "IIIAB12: Polyeder und Raumeinteilungen" , Encyclopädie der mathematischen Wissenschaften (en alemán), vol. Banda 3 (Geometrías), págs. 1-139 , Abgeschlossen am 31 de agosto de 1916  
  7. ↑ Más técnicamente, este gráfico es el 1-esqueleto; véase Grünbaum (2003) , pág. 138, y Ziegler (1995) , pág. 64.
  8. 1 2 Ziegler, Günter M. (1995), "Capítulo 4: Teorema de Steinitz para 3-politopos", Lecciones sobre politopos , Textos de posgrado en matemáticas , vol. 152, Springer-Verlag, pp. 103–126 , ISBN   0-387-94365-X
  9. ↑ Balinski, ML (1961), "Sobre la estructura gráfica de poliedros convexos en el espacio n " , Pacific Journal of Mathematics , 11 (2): 431–434 , doi : 10.2140/pjm.1961.11.431 , MR 0126765 
  10. ↑ Epifanov, GV (1966), "Reducción de un grafo plano a una arista mediante transformaciones estrella-triángulo" , Doklady Akademii Nauk SSSR (en ruso), 166 : 19–22 , MR 0201337 , Zbl 0149.21301  
  11. 1 2 Truemper, K. (1989), "Sobre la reducción delta-wye para grafos planares", Journal of Graph Theory , 13 (2): 141– 148, doi : 10.1002/jgt.3190130202 , MR 0994737 
  12. ↑ Aranguri, Santiago; Chang, Hsien-Chih; Fridman, Dylan (2022), "Desenredando grafos y curvas planares manteniendo la positividad", Actas del Simposio Anual ACM-SIAM de 2022 sobre Algoritmos Discretos (SODA) , SIAM, pp. 211–225 , doi : 10.1137/1.9781611977073.11 , ISBN  978-1-61197-707-3, MR 4415048 , S2CID 245778178  
  13. ↑ Chang, Hsien-Chih; Erickson, Jeff (2017), "Desenredando curvas planas", Discrete & Computational Geometry , 58 (4): 889–920 , arXiv : 1702.00146 , doi : 10.1007/s00454-017-9907-6 , MR 3717242 , S2CID 254027198  
  14. ↑ Barnette, David W.; Grünbaum, Branko (1969), "Sobre el teorema de Steinitz relativo a los 3-politopos convexos y sobre algunas propiedades de los grafos planares", en Chartrand, G .; Kapoor, SF (eds.), Las múltiples facetas de la teoría de grafos: Actas de la conferencia celebrada en la Western Michigan University, Kalamazoo, MI, del 31 de octubre al 2 de noviembre de 1968 , Lecture Notes in Mathematics , vol. 110, Springer, pp. 27–40 , doi : 10.1007/BFb0060102 , ISBN   978-3-540-04629-5, MR 0250916 
  15. ↑ Maxwell, J. Clerk (1864), "Sobre figuras recíprocas y diagramas de fuerzas", Philosophical Magazine , 4.ª serie, 27 (182): 250–261 , doi : 10.1080/14786446408643663
  16. ↑ Whiteley, Walter (1982), "Movimientos y tensiones de poliedros proyectados", Structural Topology , 7 : 13–38 , hdl : 2099/989 , MR 0721947 
  17. ↑ Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la Sociedad Matemática de Londres , 13 : 743–767 , doi : 10.1112/plms/s3-13.1.743 , MR 0158387 
  18. ↑ Brandes, Ulrik (2001), "Drawing on physical analogies", en Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models , Lecture Notes in Computer Science , vol. 2025, Berlín: Springer, pp. 71–86 , CiteSeerX 10.1.1.9.5023 , doi : 10.1007/3-540-44969-8_4 , ISBN    978-3-540-42062-0, MR 1880146 
  19. 1 2 Onn, Shmuel; Sturmfels, Bernd (1994), "Un teorema cuantitativo de Steinitz" , Beiträge zur Algebra und Geometrie , 35 (1): 125-129 , MR 1287206 
  20. 1 2 3 Ribó Mor, Ares; Rote, Günter; Schulz, André (2011), "Incrustaciones de cuadrículas pequeñas de 3-politopos", Discrete & Computational Geometry , 45 (1): 65– 87, arXiv : 0908.0488 , doi : 10.1007/s00454-010-9301-0 , MR 2765520 , S2CID 10141034  
  21. ↑ Brightwell, Graham R. ; Scheinerman, Edward R. (1993), "Representaciones de grafos planares", SIAM Journal on Discrete Mathematics , 6 (2): 214– 229, doi : 10.1137/0406017 , MR 1215229 
  22. 1 2 Ziegler, Günter M. (2007), "Politopos convexos: construcciones extremales y formas de vectores f . Sección 1.3: Teorema de Steinitz mediante empaquetamientos de círculos", en Miller, Ezra; Reiner, Victor; Sturmfels, Bernd (eds.), Combinatoria geométrica , IAS/Park City Mathematics Series, vol. 13, American Mathematical Society , pp. 628–642 , ISBN   978-0-8218-3736-8
  23. 1 2 Grünbaum (2003) , teorema 13.2.3, pág. 244, lo expresa en una forma equivalente donde las coordenadas son números racionales .
  24. ↑ Buchin, Kevin; Schulz, André (2010), "Sobre el número de árboles de expansión que puede tener un grafo planar", en de Berg, Mark ; Meyer, Ulrich (eds.), Algorithms - ESA 2010, 18.º Simposio Europeo Anual, Liverpool, Reino Unido, 6-8 de septiembre de 2010, Actas, Parte I , Lecture Notes in Computer Science , vol. 6346, Springer, pp. 110–121 , CiteSeerX 10.1.1.746.942 , doi : 10.1007/978-3-642-15775-2_10 , ISBN    978-3-642-15774-5, MR 2762847 , S2CID 42211547  
  25. ↑ Chrobak, Marek; Goodrich, Michael T.; Tamassia , Roberto (1996), "Dibujos convexos de grafos en dos y tres dimensiones", Actas del 12.º Simposio ACM sobre Geometría Computacional (SoCG '96) , ACM, págs. 319–328 , doi : 10.1145/237218.237401 , S2CID 1015103  
  26. ↑ Schulz, André (2011), "Dibujo de 3-politopos con buena resolución de vértices", Journal of Graph Algorithms and Applications , 15 (1): 33–52 , doi : 10.7155/jgaa.00216 , MR 2776000 
  27. ↑ Demaine, Erik D. ; Schulz, André (2017), "Incrustación de politopos apilados en una cuadrícula de tamaño polinomial", Discrete & Computational Geometry , 57 (4): 782– 809, arXiv : 1403.7980 , doi : 10.1007/s00454-017-9887-6 , MR 3639604 , S2CID 104867  
  28. ↑ Grünbaum (2003) , pág. 96a.
  29. ↑ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L. ; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012), "¿Qué hace que un árbol sea un esqueleto recto?" (PDF) , Actas de la 24.ª Conferencia Canadiense sobre Geometría Computacional (CCCG'12)
  30. ↑ Barnette, David W.; Grünbaum, Branko (1970), "Preasignación de la forma de una cara" , Pacific Journal of Mathematics , 32 (2): 299–306 , doi : 10.2140/pjm.1970.32.299 , MR 0259744 
  31. ↑ Barnette, David W. (1970), "Proyecciones de 3-politopos", Israel Journal of Mathematics , 8 (3): 304– 308, doi : 10.1007/BF02771563 , MR 0262923 , S2CID 120791830  
  32. ↑ Hart, George W. (1997), "Cálculo de poliedros canónicos" , Mathematica in Education and Research , 6 ( 3): 5–10
  33. ↑ Bern, Marshall W.; Eppstein, David (2001), "Transformaciones óptimas de Möbius para la visualización y el mallado de información", en Dehne, Frank KHA; Sack, Jörg-Rüdiger; Tamassia, Roberto (eds.), Algoritmos y estructuras de datos, 7.º Taller Internacional, WADS 2001, Providence, RI, EE. UU., 8-10 de agosto de 2001, Actas , Lecture Notes in Computer Science , vol. 2125, Springer, pp. 14–25 , arXiv : cs/0101006 , doi : 10.1007/3-540-44634-6_3 , ISBN   978-3-540-42423-9, S2CID 3266233 
  34. ^ Schramm, Oded (1992), "Cómo enjaular un huevo", Inventiones Mathematicae , 107 (3): 543– 560, Bibcode : 1992InMat.107..543S , doi : 10.1007/BF01231901 , MR 1150601 , S2CID 189830473  
  35. 1 2 3 Rivin, Igor (1996), "Una caracterización de poliedros ideales en el espacio hiperbólico tridimensional", Annals of Mathematics , Segunda Serie, 143 (1): 51– 70, doi : 10.2307/2118652 , JSTOR 2118652 , MR 1370757  
  36. ↑ Dillencourt, Michael B.; Smith, Warren D. (1996), "Condiciones de la teoría de grafos para la inscribibilidad y la realizabilidad de Delaunay" , Matemáticas Discretas , 161 ( 1–3 ): 63–77 , doi : 10.1016/0012-365X(95)00276-3 , MR 1420521 , S2CID 16382428  
  37. 1 2 Eppstein, David ; Mumford, Elena (2014), "Teoremas de Steinitz para poliedros ortogonales simples", Journal of Computational Geometry , 5 (1): 179–244 , doi : 10.20382/jocg.v5i1a10 , MR 3259910 , S2CID 8531578  
  38. 1 2 Richter-Gebert, Jürgen (1996), Espacios de realización de politopos , Lecture Notes in Mathematics , vol. 1643, Springer-Verlag, CiteSeerX 10.1.1.2.3495 , doi : 10.1007/BFb0093761 , ISBN   978-3-540-62084-6, MR 1482230 
  39. ↑ Schaefer, Marcus (2013), "Realizabilidad de grafos y enlaces", en Pach, János (ed.), Treinta ensayos sobre teoría geométrica de grafos , Nueva York: Springer, pp. 461–482 , doi : 10.1007/978-1-4614-0110-0_24 , ISBN  978-1-4614-0109-4, MR 3205168 
  40. 1 2 Eppstein, David (2020), "Treetopes y sus grafos", Discrete & Computational Geometry , 64 (2): 259– 289, arXiv : 1510.03152 , doi : 10.1007/s00454-020-00177-0 , MR 4131546 , S2CID 213885326  
  41. ↑ Hong, Seok-Hee ; Nagamochi, Hiroshi (2011), "Extending Steinitz's theorem to upper star-shaped polyhedra and spherical polyhedra", Algorithmica , 61 (4): 1022–1076 , doi : 10.1007/s00453-011-9570-x , MR 2852056 , S2CID 12622357  
  42. ^ Ciego, Roswitha ; Mani-Levitska, Peter (1987), "Rompecabezas e isomorfismos de politopos", Aequationes Mathematicae , 34 ( 2– 3): 287– 297, doi : 10.1007/BF01830678 , MR 0921106 , S2CID 120222616  
  43. ↑ Kalai, Gil (1988), "Una forma sencilla de distinguir un politopo simple de su grafo", Journal of Combinatorial Theory , Serie A, 49 (2): 381–383 , doi : 10.1016/0097-3165(88)90064-7 , MR 0964396 
  44. ↑ Ziegler, Günter M. (2008), "Superficies poliédricas de género elevado", Geometría diferencial discreta , Seminarios de Oberwolfach, vol. 38, Springer, pp. 191–213 , arXiv : math/0412093 , doi : 10.1007/978-3-7643-8621-4_10 , ISBN   978-3-7643-8620-7, MR 2405667 , S2CID 15911143  
  45. ^ Lovász, László (2001), "Representaciones de Steinitz de poliedros y el número de Colin de Verdière", Journal of Combinatorial Theory , Serie B, 82 (2): 223– 236, doi : 10.1006/jctb.2000.2027 , MR 1842113 
  46. 1 2 3 Grünbaum, Branko (2007), "Grafos de poliedros; poliedros como grafos", Matemáticas Discretas , 307 ( 3–5 ): 445–463 , doi : 10.1016/j.disc.2005.09.037 , hdl : 1773/2276 , MR 2287486 
  47. ^ Erickson, Jeff; Lin, Patrick (2020), "Una correspondencia toroidal Maxwell-Cremona-Delaunay", en Cabello, Sergio; Chen, Danny Z. (eds.), 36.º Simposio internacional sobre geometría computacional (SoCG 2020) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 164, Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, págs. 40:1–40:17, arXiv : 2003.10057 , doi : 10.4230/LIPIcs.SoCG.2020.40 , ISBN   978-3-95977-143-6, S2CID 209514295 
  48. ^ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig: Mathematisch-Physische Klasse (en alemán), 88 : 141– 164
  49. 1 2 3 Stephenson, Kenneth (2003), "Empaquetamiento de círculos: un cuento matemático" (PDF) , Notices of the American Mathematical Society , 50 (11): 1376–1388 , CiteSeerX 10.1.1.101.5592 , MR 2011604  
  50. 1 2 Andreev, EM (1970), "Polyedros convexos en espacios de Lobačevskiĭ" , Matematicheskii Sbornik , 81 (123): 445–478 , Bibcode : 1970SbMat..10..413A , doi : 10.1070/SM1970v010n03ABEH001677 , MR 0259734 
  51. ↑ Schramm, Oded (1991), "Existencia y unicidad de empaquetamientos con combinatoria especificada", Israel Journal of Mathematics , 73 (3): 321–341 , doi : 10.1007/BF02773845 , MR 1135221 , S2CID 121855202  ; véase la discusión posterior al Corolario 3.8, pág. 329
  52. ↑ Federico, Pasquale Joseph (1982), Descartes sobre los poliedros: Un estudio del "De solidorum elementis" , Fuentes en la historia de las matemáticas y las ciencias físicas, vol. 4, Springer, pág. 52  
  53. ↑ Steiner, Jakob (1832), "Pregunta 77" , Systematische Entwicklung der Abhängigkeit geometrischer Gestalten von einander (en alemán), Berlín: G. Fincke, p. 316 
  54. ^ Steinitz, Ernst (1928), "Über isoperimetrische Probleme bei konvexen Polyedern", Journal für die Reine und Angewandte Mathematik (en alemán), 1928 (159): 133– 143, doi : 10.1515/crll.1928.159.133 , MR 1581158 , S2CID 199546274