1. Sistemas de Rotación

Modelo combinatorio de grafos encajados

Sistemas de Rotación

Motivación

Queremos codificar encajes celulares de grafos en superficies orientables sin dibujar la superficie, usando sólo datos combinatorios.

  • Entrada: un grafo abstracto \(G\)
  • Dato extra: un sistema de rotación (orden cíclico local)
  • Salida: una superficie orientable donde \(G\) queda encajado, más las caras y el género

La idea es que la información “local” (en vértices) determine completamente la estructura “global” (la superficie).

Semiaristas (Darts o Half-Edges)

Para trabajar con sistemas de rotación, descomponemos cada arista del grafo \(G\) mediante una partición formal. Insertamos un vértice ficticio (o de paso) en el interior de cada arista, lo que resulta en un conjunto \(D\) de semiaristas (también llamadas darts o half-edges).

Esta construcción garantiza que:

  • Partición por Arista: Cada arista original queda particionada exactamente en dos semiaristas que comparten el vértice ficticio.
  • Incidencia en Vértices Originales: Cada semiarista \(d \in D\) tiene un extremo en un vértice original de \(G\) y el otro en un vértice ficticio. Decimos que \(d\) está asociada al vértice original donde incide.
  • Relación de Adyacencia (Involución): Dos semiaristas son adyacentes si comparten el mismo vértice ficticio. Esto define una permutación \(\rho: D \to D\) compuesta por trasposiciones (2-ciclos), donde cada ciclo vincula el par de semiaristas que conforman una arista original.
NotaConteo de semiaristas

Si el grafo tiene \(E\) aristas, tendremos \(|D| = 2E\) semiaristas en total, donde \(D\) es el conjunto de todas las semiaristas.

Ejemplo 1: Un vértice, dos lazos

Consideremos el grafo con un vértice y dos aristas.

Construcción

  • Vértices: 1
  • Aristas: 2 aristas
  • Semiaristas: 4 (etiquetadas 1, 2, 3, 4)

Etiquetado de semiaristas

Definición: Sistema de Rotación

Un sistema de rotación sobre un grafo \(G\) se define por un par de permutaciones \((\sigma, \rho)\) sobre el conjunto de semiaristas \(D\):

Permutación \(\sigma\) (vértices)

  • Es un producto de ciclos disjuntos
  • Hay un ciclo por cada vértice de \(G\)
  • Cada ciclo describe el orden cíclico de las semiaristas incidentes a ese vértice
  • El orden cíclico refleja cómo las aristas se ordenan alrededor del vértice en la superficie

Permutación \(\rho\) (aristas)

  • Es un producto de 2-ciclos (transposiciones)
  • Cada 2-ciclo empareja las dos semiaristas que forman una arista
  • Es una involución sin puntos fijos: \(\rho^2 = \mathrm{id}\)
NotaContexto Histórico y Terminología

Los sistemas de rotación tienen una rica historia y han sido redescubiertos en múltiples contextos:

  • Orígenes: Fueron introducidos por Edmonds (1960) y formalizados por Youngs (1963), quien también introdujo sistemas con signo para superficies no orientables. Representaciones similares fueron propuestas independientemente por Jacques, Biggs, y Walsh & Lehman.
  • Desarrollo: Tutte y Gross & Alpert extendieron estos sistemas. El encaje celular inducido que revisaremos más adelante es frecuentemente llamado encaje de Heffter-Edmonds.
  • Sinónimos: En la literatura se encuentran como vortex graphs, constelaciones, mapas combinatorios, fat graphs, ribbon graphs y dessins d’enfants.

Nuestra Convención: Adoptamos la notación de SageMath y Lando & Zvonkin, usando el par de permutaciones \((\sigma, \rho)\) sobre semiaristas y refiriéndonos a la estructura topológica como Ribbon Graph.

Ejemplo: Un vértice, dos lazos

Recordando la construcción del ejemplo anterior:

  • Vértices: 1
  • Aristas: 2
  • Semiaristas: 4 (etiquetadas 1, 2, 3, 4)

Es importante notar que \(\rho\) está fijo por la construcción del grafo (la elección de qué pares de semiaristas forman cada arista). Por lo tanto, solo podemos variar \(\sigma\).

Como tenemos 4 semiaristas incidentes al mismo vértice, el número de posibles órdenes cíclicos es \((4-1)! = 6\). A continuación listamos todas las posibilidades:

  1. \(\sigma = (1, 2, 3, 4)\), \(\rho = (1, 2)(3, 4)\)
  2. \(\sigma = (1, 2, 4, 3)\), \(\rho = (1, 2)(3, 4)\)
  3. \(\sigma = (1, 3, 2, 4)\), \(\rho = (1, 2)(3, 4)\)
  4. \(\sigma = (1, 3, 4, 2)\), \(\rho = (1, 2)(3, 4)\)
  5. \(\sigma = (1, 4, 2, 3)\), \(\rho = (1, 2)(3, 4)\)
  6. \(\sigma = (1, 4, 3, 2)\), \(\rho = (1, 2)(3, 4)\)

Cada una de estas elecciones define un sistema de rotación válido. En las siguientes secciones veremos cómo estas permutaciones determinan la topología de la superficie resultante.

Ejemplo 2: Triángulo K₃

Consideremos el grafo completo con 3 vértices: \(K_3\):

Construcción

  • Vértices: 3 (A, B, C)
  • Aristas: 3 (AB, BC, CA)
  • Semiaristas: 6 (etiquetadas 1, 2, 3, 4, 5, 6)

Asignación de semiaristas:

  • Vértice A: semiaristas 1, 6
  • Vértice B: semiaristas 2, 3
  • Vértice C: semiaristas 4, 5

Aristas:

  • AB: semiaristas 1 y 2
  • BC: semiaristas 3 y 4
  • CA: semiaristas 5 y 6

Para definir el sistema de rotación, la asignación explícita de semiaristas es necesaria para fijar \(\rho\).

  • \(\rho\): Queda determinado por los pares que forman las aristas. \[\rho = (1, 2)(3, 4)(5, 6)\]

  • \(\sigma\): En este caso, como cada vértice tiene grado 2, existe un único orden cíclico posible para las semiaristas incidentes (\((a,b)\) es equivalente a \((b,a)\)). \[\sigma = (1, 6)(2, 3)(4, 5)\]

Este sistema describe el encaje estándar de \(K_3\) en la esfera (género 0).

El “Big Bang” Combinatorio: ¿Cuántos encajes existen?

Para un grafo dado (sin vértices aislados), podemos calcular exactamente cuántos Sistemas de Rotación (que generan superficies orientables) se pueden construir. La fórmula depende enteramente de la conectividad local de los vértices.

La Fórmula de Conteo

Si llamamos \(N(G)\) al número total de sistemas de rotación para un grafo \(G\), tenemos:

\[ N(G) = \prod_{v \in V(G)} (\deg(v) - 1)! \]

Donde:

  • \(\prod\): Es el símbolo de producto (multiplicamos el resultado de cada vértice).
  • \(V(G)\): Es el conjunto de todos los vértices del grafo.
  • \(\deg(v)\) (Grado): Es el número de semiaristas que llegan al vértice \(v\).
  • \((\deg(v) - 1)!\): Es el número de formas de organizar las semiaristas en un círculo (permutaciones cíclicas).

Verificación de nuestros ejemplos

  1. El grafo de un vértice y dos lazos:
    • Tenemos 1 vértice con grado \(4\).
    • Cálculo: \((4-1)! = 6\) sistemas.
    • Resultado: Coincide exactamente con la lista de \(6\) que vimos anteriormente.
  2. El Triángulo (\(K_3\)):
    • Tenemos 3 vértices, cada uno con grado \(2\).
    • Cálculo: \((2-1)! \times (2-1)! \times (2-1)! = 1\) sistema.
    • Resultado: Por eso el \(K_3\) es “rígido”; solo puede encajarse de una forma (en la esfera).

¿Cómo crece el problema? (El caso de los Grafos Completos \(K_n\))

A medida que añadimos vértices y cada uno se conecta con todos los demás, el número de universos topológicos posibles crece de forma estrepitosa:

Grafo Vértices Grado Fórmula Total de Sistemas
\(K_3\) (Triángulo) 3 2 \((1!)^3\) 1
\(K_4\) (Tetraedro) 4 3 \((2!)^4\) 16
\(K_5\) (Pentáculo) 5 4 \((3!)^5\) 7,776
\(K_6\) 6 5 \((4!)^6\) 191,102,976
\(K_7\) 7 6 \((5!)^7\) 358,318,080,000,000

Nota para la reflexión: ¡Para un simple grafo de 7 vértices, existen más de 358 billones de formas de encajarlo en superficies! La gran mayoría de estas formas resultarán en superficies con muchísimos “agujeros” (género alto), y solo unas pocas tendrán género mínimo (\(K_7\) no es planar).

Interpretación geométrica

El sistema de rotación \((\sigma, \rho)\) codifica:

  1. El grafo subyacente
    • Los ciclos de \(\sigma\) determinan los vértices
    • Los 2-ciclos de \(\rho\) determinan las aristas
    • Podemos reconstruir \(G\) desde \((\sigma, \rho)\)
  2. El orden cíclico local
    • Cada ciclo de \(\sigma\) indica cómo se ordenan las semiaristas alrededor de un vértice
    • Este orden respeta la orientación de la superficie

Construcción en SageMath

SageMath implementa ribbon graphs directamente desde sistemas de rotación.

Ejemplo 1: Un vértice, dos lazos

Construyamos el sistema de rotación más estándar para este grafo:

Prueba el código directamente aquí (haz clic en “Ejecutar”):

Ejemplo 2: Triángulo K₃ con numeración salteada

Podemos etiquetar las semiaristas con cualquier numeración, no necesariamente 1,2,3,…

Prueba el código directamente aquí (haz clic en “Ejecutar”):

Implementando la fórmula de conteo

Podemos calcular programáticamente cuántos sistemas de rotación existen para un grafo dado:

Prueba el código directamente aquí (haz clic en “Ejecutar”):

Ejercicios

TipEjercicio 1

Considera un grafo con un vértice y tres self-loops (tres aristas que comienzan y terminan en el mismo vértice).

  1. ¿Cuántas semiaristas tiene este sistema?
  2. ¿Cuántos sistemas de rotación posibles existen para este grafo? Usa la fórmula manualmente.
  3. Escribe en Sage un sistema de rotación \((\sigma, \rho)\) para este grafo usando PermutationGroupElement.
  4. Usa la función contar_sistemas(R) del ejemplo para verificar tu cálculo del inciso (b).
TipEjercicio 2

Experimentando con numeración y normalización:

  1. Crea un RibbonGraph usando numeración salteada (por ejemplo, usando solo números pares o múltiplos de 5).
  2. Usa el método .normalize() para obtener la versión canónica.
  3. Verifica que el número de semiaristas se preserva usando len(R.sigma().domain()).
  4. ¿Qué propiedades del grafo cambian con normalize() y cuáles se preservan?

Referencias

  • [GGD2011] E. Girondo, G. Gonzalez-Diez, Introduction to Compact Riemann surfaces and Dessins d’enfant, London Mathematical Society, Student Text 79, 2011.
  • [LZ2004] S. Lando, A. Zvonkine, Graphs on Surfaces and Their Applications, Springer-Verlag, 2004.
  • [Edmonds1960] J. Edmonds, A Combinatorial Representation for Polyhedral Surfaces, Notices Amer. Math. Soc. 7, 1960. (Tesis disponible en UMD)
  • [Youngs1963] J. W. T. Youngs, The Genus of a Graph, Journal of Mathematics and Mechanics, Vol. 12, No. 2, 1963. JSTOR
ImportanteCambio de Perspectiva: El Mapa es el Territorio

Hasta ahora, hemos hablado de “poner un grafo sobre una superficie”. Sin embargo, en la práctica computacional (y en SageMath), el grafo abstracto y la superficie no existen antes de definir las permutaciones.

Es fundamental entender que el par combinatorio \((\sigma, \rho)\) ES el objeto.

No “buscamos” un encaje para un sistema de rotación. El sistema de rotación construye su propia superficie única e inevitable.

En la siguiente sección, veremos cómo estas permutaciones “tejen” la superficie automáticamente, sin necesidad de dibujarla.

Publicado el 06 de febrero de 2026

Volver arriba

Reutilización