Invariants of almost embeddings of graphs in the plane

Este artículo establece relaciones entre invariantes de casi incrustaciones de grafos en el plano, conecta estos resultados con la homología del producto eliminado del grafo, construye ejemplos que realizan ciertos valores de dichos invariantes y presenta conceptos de topología algebraica y geométrica de manera accesible para no especialistas, incluyendo conjeturas y problemas abiertos.

Lo esencial

Imagina que tienes un grupo de amigos (los vértices de un gráfico) y quieres organizar una fiesta en una habitación plana (el plano). Algunos amigos se conocen entre sí y necesitan estar conectados por una cuerda (aristas).

El problema clásico es: ¿Puedes dibujar a todos tus amigos y sus cuerdas en el suelo sin que ninguna cuerda se cruce con otra? Si puedes, el gráfico es "planar" (como un mapa de metro limpio). Si no puedes (como en el famoso caso de los cinco amigos que todos quieren hablar con todos, o el caso de dos grupos de tres que se conectan entre sí), el gráfico es "no planar".

Pero, ¿qué pasa si permitimos que las cuerdas se crucen, pero solo bajo reglas muy estrictas? Aquí es donde entra este fascinante artículo de matemáticas.

1. ¿Qué es un "casi-empotramiento"? (La fiesta con reglas)

Los autores, Alkin, Miroshnikov y Skopenkov, estudian algo llamado "casi-empotramiento" (almost embedding).

Imagina que estás dibujando tu gráfico en el suelo. La regla del "casi-empotramiento" es muy simple pero poderosa:

• Regla de oro: Dos cuerdas que conectan a amigos que no se conocen entre sí nunca pueden tocarse.
• Excepción: Las cuerdas sí pueden tocarse si conectan a amigos que sí se conocen (es decir, si comparten un vértice).

Es como si en la fiesta, dos personas que no se hablan nunca pudieran chocar accidentalmente, pero si se conocen, pueden abrazarse o cruzarse sin problemas.

2. El "Número de Vueltas" (La brújula mágica)

Para entender si un dibujo cumple estas reglas, los matemáticos usan un número mágico llamado número de vueltas (winding number).

La analogía del bailarín:
Imagina que tienes un punto fijo en el suelo (un amigo que no se mueve). Ahora, toma una cuerda que conecta a dos otros amigos y hazla "bailar" alrededor de ese punto fijo.

• Si la cuerda da una vuelta completa en sentido contrario a las agujas del reloj, el número es +1.
• Si da una vuelta en sentido horario, es -1.
• Si no da vueltas, es 0.
• Si da tres vueltas locas, es +3.

Este número nos dice cuántas veces la cuerda "rodea" a la persona que no debería tocarla.

3. Los Números Mágicos: Cíclicos y Triodicos

El artículo introduce dos nuevos "números mágicos" para medir el caos en estos dibujos:

• Número Cíclico (Cyclic number): Imagina tres amigos formando un triángulo. Si las cuerdas que los unen forman un patrón de baile muy específico alrededor de ellos, este número mide cuántas veces el triángulo "gira" sobre sí mismo.

  • La sorpresa: Siempre resulta ser un número impar (1, 3, 5...). Nunca es par. Es como si la naturaleza dijera: "En este tipo de fiestas, siempre hay un número impar de giros".

• Número Triódico (Triodic number): Imagina un amigo en el centro (como un poste de teléfono) conectado a tres amigos alrededor. Este número mide cómo las cuerdas que salen del poste giran alrededor de los otros.

  • La sorpresa: ¡También es siempre un número impar!

4. El Gran Descubrimiento: ¿Cuánto caos es posible?

El artículo responde a una pregunta profunda: ¿Podemos crear cualquier cantidad de caos (vueltas) que queramos, siempre que respetemos la regla de "casi-empotramiento"?

• Para el gráfico K4 (4 amigos todos conectados):
  Los autores demuestran que puedes tener cualquier combinación de números de vueltas, siempre que la suma total de esos números sea un número impar.

  • Ejemplo: Puedes tener un amigo rodeado 100 veces, otro 5 veces, otro 2 veces y otro 0 veces, siempre que la suma total sea impar. ¡Es como si pudieras hacer girar las cuerdas tan locamente como quieras, pero la "paridad" (impar) debe mantenerse!

• Para el gráfico K5 (5 amigos todos conectados) sin una cuerda:
  Aquí la cosa se pone más interesante. Si intentas dibujar 5 amigos todos conectados (lo cual es imposible sin cruces), pero quitas una cuerda, descubren que la diferencia entre las vueltas de dos amigos específicos siempre debe ser un número impar.

  • El hallazgo reciente: Un matemático llamado Timur Garaev (citado en el artículo) demostró que esta diferencia no solo es impar, ¡sino que siempre es +1 o -1! No puede ser 3, 5 o 100. Es una restricción muy fuerte. Es como si la física del plano dijera: "Solo puedes tener un giro extra, ni más ni menos".

5. ¿Por qué importa esto? (Más allá de los gráficos)

Parece un juego de cuerdas, pero tiene aplicaciones reales y profundas:

1. Geometría y Topología: Ayuda a entender cómo se pueden deformar formas en el espacio sin romperlas.
2. Informática: Es útil para diseñar circuitos en chips o rutas de redes donde los cables no deben cruzarse de ciertas formas.
3. Matemáticas Puras: Estos números (llamados invariantes) son como las "huellas dactilares" de un dibujo. Si dos dibujos tienen números diferentes, ¡son fundamentalmente diferentes y no se pueden transformar uno en el otro sin romper la regla!

En resumen

Este artículo es como un manual de instrucciones para un juego de cuerdas en el suelo. Los autores nos dicen:

1. Si permites cruces controlados, puedes medir el "giro" de las cuerdas.
2. Estos giros siempre siguen reglas estrictas (siempre son números impares).
3. Para algunos gráficos, puedes hacer giros locos (cualquier número), pero para otros (como el de 5 amigos), la naturaleza te pone un límite muy estricto: solo un giro extra permitido.

Es una demostración hermosa de cómo, incluso en el caos de los cruces, las matemáticas mantienen un orden secreto y elegante.

Resumen técnico

Aquí presento un resumen técnico detallado del artículo "Invariantes de casi-empotrados de grafos en el plano" (Invarianty pochti vlozheniy grafov v ploskost), escrito por E. Alkin, A. Miroshnikov y A. Skopenkov.

1. Planteamiento del Problema

El artículo aborda el problema de clasificar y entender las propiedades topológicas de las casi-empotradas (o almost embeddings) de grafos en el plano $\mathbb{R}^2$.

• Definición: Una aplicación $f: K \to \mathbb{R}^2$ de un grafo $K$ se denomina casi-empotrada si las imágenes de cualquier par de símplices no adyacentes (vértices o aristas) no se intersectan. Es decir, las aristas que no comparten vértices no se cruzan, y ningún vértice cae sobre una arista no incidente.
• Contexto: A diferencia de los empotrados estrictos (grafos planares), las casi-empotradas permiten intersecciones entre aristas adyacentes o entre una arista y un vértice adyacente, pero mantienen la separación de componentes no adyacentes. Este concepto es crucial en geometría combinatoria, topología algebraica y el estudio de hipergrafos.
• La cuestión central: ¿Qué valores pueden tomar los invariantes enteros asociados a estas casi-empotradas? Específicamente, el artículo busca describir el conjunto de valores posibles para ciertas cantidades topológicas (números de giro, números cíclicos y triódicos) y establecer relaciones algebraicas entre ellos.

2. Metodología

Los autores emplean una combinación de topología algebraica, teoría de grafos y geometría combinatoria. La metodología se basa en los siguientes pilares:

• Invariantes Numéricos: Se definen y analizan tres tipos principales de invariantes enteros asociados a las casi-empotradas:
  1. Números de giro (Winding numbers): $w_f(C, v)$, que miden el número de vueltas que da una curva cerrada (imagen de un ciclo $C$) alrededor de un punto (imagen de un vértice $v$).
  2. Números cíclicos (Cyclic numbers): $cy_f$, definidos para ternas de curvas que forman un triángulo topológico.
  3. Números triódicos (Triod numbers): $tr_f$, definidos para ternas de curvas que se unen en un punto central (estructura de tipo "Y" o triodo).
• Espacio de Configuraciones y Producto Eliminado: Se utiliza el concepto del producto eliminado (o cuadrado eliminado) $\tilde{K}$, que es el subconjunto de $K \times K$ formado por pares de puntos distintos. La estructura de este espacio y sus grupos de homología $H_1(\tilde{K}; \mathbb{Z})$ son fundamentales para entender las relaciones entre los invariantes.
• Herramientas Topológicas Clásicas:
  • Teorema de Borsuk-Ulam: Se utiliza para probar la paridad (imparidad) de ciertos invariantes.
  • Teorema de Radon y Hanani-Tat: Se generalizan versiones cuantitativas de estos teoremas clásicos sobre la no planaridad de $K_5$ y $K_{3,3}$.
  • Homología del Cuadrado Eliminado: Los autores demuestran que los invariantes pueden interpretarse como homomorfismos desde el grupo de homología del cuadrado eliminado hacia los enteros.
• Construcciones Constructivas: Para demostrar que ciertos valores son realizables, los autores construyen explícitamente casi-empotradas utilizando técnicas de "movimientos de dedos" (finger moves), que permiten modificar localmente las curvas para cambiar los números de giro sin violar la condición de casi-empotrada.

3. Contribuciones Clave y Resultados

El artículo presenta una serie de teoremas y resultados que conectan invariantes discretos con estructuras algebraicas profundas:

A. Relaciones entre Invariantes para $K_4$

• Teorema 4.2: Para cualquier casi-empotrada de $K_4$, la suma alternada de los números de giro $W_f = \sum (-1)^j w_f(j)$ es siempre un número impar. Esto es una versión cuantitativa de la no planaridad de ciertos subgrafos.
• Teorema 4.3 (Resultado Reciente): Se demuestra que, para $K_4$, no existen restricciones adicionales más allá de la paridad. Es decir, para cualquier cuaterna de enteros $(n_1, n_2, n_3, n_4)$ cuya suma alternada sea impar, existe una casi-empotrada que realiza esos valores exactos.
• Conexión con Números Cíclicos y Triódicos: Se establecen fórmulas explícitas que relacionan los números de giro con los números cíclicos y triódicos (Teorema 8.2). Por ejemplo, $2w_f(j) = cy_f(j) + (-1)^j tr_f(j)$. Esto permite expresar todos los invariantes en términos de un conjunto base.

B. Extensiones a $K_5$ y $K_{3,3}$

• Teorema 5.3: Para el grafo $K_5$ menos una arista, la diferencia de los números de giro asociados a dos ciclos específicos es siempre impar.
• Resultado de Garaev (Teorema 5.3.b): Se cita y discute un resultado profundo de T. Garaev que establece que para $K_5$ menos una arista, la diferencia de números de giro es exactamente $\pm 1$ (no cualquier número impar). Esto contrasta con el caso de $K_4$, donde los valores pueden ser arbitrariamente grandes.
• Teorema 5.6: Para $K_{3,3}$ menos una arista, la diferencia de números de giro es impar.

C. Números de Wu y Homología

• Generalización (Sección 9): Los autores introducen los números de Wu ($C$-números), parametrizados por elementos del grupo de homología $H_1(\tilde{K}; \mathbb{Z})$.
• Teoremas 9.6 y 9.7: Se demuestra que cualquier número de Wu puede expresarse como una combinación lineal racional de los números de giro, cíclicos y triódicos. Esto unifica todos los invariantes estudiados bajo un marco algebraico común.
• Problema de Descripción (Problema 6.1 y 9.5): Se formula el problema abierto de describir completamente el conjunto de valores realizables por casi-empotradas para grafos generales. Se resuelve completamente para $K_4$ y se plantean conjeturas para $K_5$ menos una arista.

D. Clasificación y Isotopía

• Teorema 10.1: Se establece que dos empotrados de un grafo conexo en el plano son isotópicos si y solo si sus restricciones a cualquier triodo y a cualquier ciclo no auto-intersectante son isotópicos.
• Se discute la diferencia entre casi-isotopía e isotopía, mostrando que los invariantes estudiados son invariantes bajo casi-isotopía, pero no necesariamente clasifican completamente las clases de casi-empotradas (a diferencia de los empotrados estrictos).

4. Significado e Impacto

Este trabajo es significativo por varias razones:

1. Puente entre Topología y Combinatoria: Proporciona una visión accesible (aunque rigurosa) de conceptos avanzados de topología algebraica (homología de productos eliminados, teorema de Borsuk-Ulam) aplicados a problemas concretos de teoría de grafos.
2. Resolución de Casos Específicos: Resuelve el problema de la realizabilidad de invariantes para el grafo $K_4$, mostrando que la única restricción es la paridad, lo cual es un resultado sorprendente y no trivial.
3. Conexión con la No-Planaridad: Ofrece una perspectiva cuantitativa y algebraica sobre por qué ciertos grafos no son planares, generalizando el teorema de Hanani-Tat y el teorema de van Kampen-Flores.
4. Herramientas para Dimensiones Superiores: Las técnicas desarrolladas (especialmente el uso del producto eliminado y los números de Wu) son fundamentales para el estudio de empotrados de complejos simpliciales en espacios de dimensión superior, un área activa de investigación en topología combinatoria.
5. Problemas Abiertos: El artículo deja planteadas conjeturas importantes, como la descripción completa de los valores realizables para $K_5$ menos una arista y la clasificación de casi-empotradas para árboles y otros grafos, guiando la investigación futura.

En resumen, el artículo no solo recopila y simplifica definiciones existentes, sino que aporta nuevos teoremas de realizabilidad, establece conexiones profundas entre invariantes topológicos discretos y la estructura de homología de los grafos, y abre nuevas vías para la comprensión de las restricciones geométricas en el plano.