¿Por qué los gráficos planos son tan excepcionales?

Question

En comparación con las clases de gráficos incrustados en otras superficies.

Algunas formas en las que son excepcionales:

1. El criterio de Mac Lane y Whitney son las caracterizaciones algebraicas de los gráficos planares. (Bueno, mayormente algebraico en el primer caso.) Antes de escribir esta pregunta, no sabía si existían generalizaciones a los gráficos incrustados en otras superficies, pero por suerte Google-fu encontró algunas referencias -- en particular parece haber una generalización del criterio de Whitney debido a Jack Edmonds para las superficies generales, aunque frustrantemente no puedo encontrar el papel, y la principal referencia que encontré implica que podría haber un pequeño problema en la botella de Klein. ¿Alguien sabe si el resultado de Edmonds es tan fácil de probar como el de Whitney?

2. La clásica caracterización de Kuratowski de los gráficos planares de los menores prohibidos. Por supuesto que esto se generaliza a otras superficies, pero esto resultado es a la vez increíblemente profundo y difícil (a diferencia de la prueba de Kuratowski, que no es de ninguna manera trivial pero que puede obtenerse por un estudiante universitario suficientemente dedicado - en realidad, mi trabajo como ejercicio es en gran medida lo que motivó la pregunta) y es en cierto sentido "esencialmente combinatorio" en el sentido de que se aplica a una clase más amplia de familias que no están intrínsecamente definidas topológicamente.

3. En la otra dirección de la dificultad, el teorema de los cuatro colores. Aparentemente no es difícil demostrar (excepto por el avión) que lo que resulta ser el estrecho límite superior en el número cromático de un gráfico incrustado en una superficie (que no sea, por la razón que sea, la botella de Klein) es, de hecho, un límite superior ¡el problema es mostrar la estanqueidad! Mientras que es bastante trivial mostrar que $K_4$ es plana (para ser justos, sin embargo, la estanqueidad es fácil de comprobar para superficies de género pequeño - el problema está en el caso general), pero el teorema de los cuatro colores requiere cantidades inhumanas de cálculo y métodos muy diferentes, esencialmente ad-hoc.

Me doy cuenta de que la esfera tiene el género 0, lo que la hace única, y tiene un grupo fundamental trivial, que es lo mismo, pero mientras me imagino que esta información es relacionado a la excepcionalidad del plano/esfera, no es realmente tan satisfactoria como una respuesta. Entonces, ¿por qué es que los métodos que funcionan en todas partes tienden a fallar en la esfera?

Preguntas relacionadas: Razones para la importancia de la planitud y la coloración

Answer 1

Como señala Gil Kalai, el Teorema de Steinitz (Un gráfico G es el gráfico de vértice de un poliedro tridimensional convexo, si y sólo si G es plano y está conectado en 3 dimensiones) es muy poderoso. Significa que las propiedades combinatorias (circuitos hamiltonianos, emparejamientos, etc.) de algo tridimensional pueden ser estudiadas mirando un tipo especial de gráfico en 2 dimensiones. Nada completamente parecido a esto sucede para los politopos convexos de mayor dimensión. De manera similar, no sabemos cómo estudiar todos los "politopos toroidales" usando una clase especial de gráficos en el toro.

Lo que parece intrigante es la interfaz entre la captura de las propiedades "geométricas" de los objetos a partir de las propiedades combinatorias (teoría de gráficos). Por ejemplo, desde hace algún tiempo me interesa saber qué poliedros convexos tridimensionales, con todas sus caras siendo triángulos, pueden ser realizados con triángulos isósceles como caras. Una forma de atacar esto es mirar los gráficos planos de 3 conexiones con al menos 4 vértices cuyas caras son triángulos (gráficos planos máximos). Resulta que uno puede colorear los bordes de tal gráfico con dos colores a y b para que cada cara obtenga dos bordes a y un borde b. Ahora uno puede preguntarse si estas coloraciones pueden realizarse con triángulos isósceles congruentes, ya que los colores a y b se utilizan para codificar las dos longitudes de los bordes de los triángulos isósceles congruentes. No es difícil mostrar que algunos gráficos planares máximos no pueden ser realizados con triángulos isósceles congruentes, pero decir exactamente qué gráficos pueden ser realizados así parece mucho más difícil. Además, la teoría de gráficos me permitió ver muchas formas de realizar tales poliedros geométricamente, cuando tal realización es posible - en otras palabras, el mismo tipo de combinación a menudo puede realizarse con triángulos isósceles congruentes de muchas maneras), además de las formas que tienen mucha simetría. Si 4 divide el número de caras de un gráfico plano máximo se puede colorear sus bordes con dos colores a y b para que el número de triángulos a, a, b y b, a sean iguales. Sin embargo, no he podido decir explícitamente cuando tales coloraciones se traducen en realizaciones geométricas. Hablando en términos generales, las preguntas combinatorias parecen "fáciles" mientras que las geométricas parecen "difíciles". No sé si las máximas gráficas planas con al menos 4 vértices pueden ser realizadas por poliedros convexos con triángulos isósceles. (Mi conjetura es que sí.) También hay preguntas interesantes cuando se permiten mezclas de triángulos isósceles y triángulos equiláteros. (Se sabe que hay exactamente 8 poliedros convexos con sólo triángulos equiláteros para las caras). Uno de los puntos conflictivos de estas preguntas es tratar de decir cuando dos triángulos que comparten un borde en el gráfico se aplanan y quedan en un plano en la realización en el espacio 3.

Mi punto es que el Teorema de Steinitz permitió el progreso en muchas cuestiones y me animó a formular nuevas preguntas geométricas que no se me hubieran ocurrido de otra manera.

Mejor,

Joe Malkevitch

Answer 2

(Creo que la cuestión de por qué los gráficos planares son excepcionales es importante. Se puede preguntar no sólo en el contexto de los gráficos incrustados en otras superficies. Permítanme editar y elaborar, también tomando prestado de las observaciones.)

La dualidad: Tal vez la dualidad es la propiedad crucial de los gráficos planares. Hay un teorema que afirma que el dual de un matroide gráfico M es un matroide gráfico si y sólo si M es el matroide de un gráfico plano. En este caso, el dual de M es el matroide del gráfico dual de G. (Ver este artículo de wikipedia ). Esto significa que los circuitos de un gráfico plano se corresponden uno a uno con los cortes del gráfico dual.

Una importante manifestación de la singularidad de los gráficos planos (que creo que está relacionada con la dualidad) es la fórmula de Kasteleyn para el número de coincidencias perfectas y la conexión con el conteo de árboles.

Robustas descripciones geométricas: Otra diferencia conceptual es que los gráficos planares (3-conectados o máximos) son gráficos de politopos tridimensionales convexos y, por lo tanto, tienen propiedades geométricas adicionales que los gráficos de las superficies no comparten.

La definición geométrica de los gráficos planares (a diferencia de varias generalizaciones) es muy robusta. Un gráfico es plano si puede dibujarse en el plano de manera que los bordes no se intersecten en su interior y se representen mediante curvas de Jordania; la clase de gráficos planos es también lo que obtenemos si sustituimos "curvas de Jordania" por "intervalos de líneas", o si sustituimos "sin intersección" por "número par de cruces". El teorema de Koebe-Andreev-Thurston permite representar cada gráfico plano por el "gráfico en contacto" de círculos no superpuestos. Ambas representaciones (relacionadas) por medio de politopos convexos y por empaquetamiento de círculos, pueden respetar el conjunto de automorfismos del gráfico y su dual.

Construcciones inductivas simples. Otra propiedad excepcional de la clase de gráficos planares es que los gráficos planares pueden ser construidos por simples construcciones inductivas. (A este respecto son similares a la clase de los árboles, aunque las construcciones inductivas no son tan simples como para los árboles). Esto falla en la mayoría de las generalizaciones de los gráficos planares.

Una importante propiedad relacionada de los gráficos, mapas y triangulaciones planas (con vértices etiquetados) es que se pueden enumerar muy bien. Esta es la teoría de Tutte. (Tiene profundas extensiones en las superficies).

A menudo, los resultados sobre los gráficos planares se extienden a otras clases. Como mencioné, la teoría de Tutte se extiende a las triangulaciones de otras superficies. Otro ejemplo es el teorema fundamental de separación Lipton-Tarjan, que se extiende a todos los gráficos con un menor prohibido.

El estudio de los gráficos planares ha llevado a importantes conceptos teóricos de los gráficos Otra razón (de naturaleza diferente) por la que los gráficos planares son excepcionales es que varios conceptos teóricos importantes sobre los gráficos fueron descubiertos al observar los gráficos planares (o los gráficos planares especiales). La noción de coloración de los vértices de los gráficos surgió (hasta donde yo sé) de la conjetura de los cuatro colores sobre los gráficos planares. De manera similar, los caminos y ciclos Hamiltonianos fueron estudiados por primera vez para los gráficos planares.

---

Gráficos en las superficies y otras nociones que generalizan la planitud. Considerar la clase de todos los gráficos que pueden ser incrustados en una superficie dada es una extensión natural e importante de la planitud. Pero, de hecho, para varias cuestiones, los gráficos incrustados en las superficies pueden no ser la generalización correcta de los gráficos planares.

David Eppstein mencionó otra generalización a través de la invariante de Colin de Verdier. Esto describe un hiearachy de gráficos donde la siguiente clase después de los gráficos planares son "gráficos incrustados sin líneas". Esos son gráficos que pueden ser incrustados en el espacio sin tener dos cilindros desarticulados unidos geométricamente. Resultó que esta es también una noción muy robusta y conduce a una hermosa clase de gráficos. (Todos tienen como máximo 4v-10 bordes donde v es el número de vértices; El caso conocido de la conjetura de Hadwiger para los gráficos que no tienen K_6 menor implica que todos ellos son 5 coloreables). Otras clases en esta jerarquía son todavía muy misteriosas. Otras extensiones de la planitud son: 3) (no literalmente) Gráficos que no tienen K_r como menor; 4;5) (Ambos muy problemáticos) Como Joe mencionó, gráficos de d-polítopos, y también gráficos obtenidos de empaques de esferas en dimensiones mayores; 6) (no gráficos) complejos simplificados r-dimensionales que no pueden ser incrustados en el doble de la dimensión, 7) Gráficos (y esqueletos) de un politono d con un segundo número g (tórico) que se desvanece, y muchos más.

Menores de edad y coloración prohibidos. En cuanto al segundo y tercer punto de la pregunta. Sobre la coloración, no estoy seguro de si debemos considerar los gráficos planares de 4 colores y los gráficos de coloración en otras superficies como fenómenos muy relacionados. En cuanto a los menores prohibidos. El teorema de Kuratowski sobre superficies es un caso especial (y también un importante paso de la prueba) de un resultado mucho más general (la conjetura de Wagner probada por Robertson y Seymour) sobre cualquier clase de gráficos cerrados para menores. Este resultado puede considerarse como una ampliación del teorema de Kuratowski y también (y quizás más importante) una ampliación del teorema de Kruskal y Nash-Williams sobre los árboles. De hecho, el teorema de Kuratoski se relaciona muy bien con el cuadro más general de la obstrucción topológica a la incrustación. Si se quiere proponer una comprensión diferente (quizás topológica) de la extensión del teorema de Kuratowski para las superficies, entonces quizás se debería comenzar por el bien-cuasi ordenado teorema de los árboles.

Answer 3

Otra caracterización (menos conocida) de los gráficos planares es El teorema de Schnyder , que caracteriza los gráficos planares según dimensión de orden. Es decir, un gráfico es plano si y sólo si su incidencia poset tiene una dimensión de orden como máximo 3.

Además, sería negligente no mencionar la hermosa (fuerte) Teorema de Hanani-Tutte :

Un gráfico es plano si y sólo si tiene un dibujo en el plano de tal manera que cada dos bordes no adyacentes cruzan un incluso número de veces.