En matemáticas combinatorias , los sistemas de rotación (también llamados incrustaciones combinatorias o mapas combinatorios ) codifican incrustaciones de grafos en superficies orientables al describir el ordenamiento circular de las aristas de un grafo alrededor de cada vértice. Una definición más formal de un sistema de rotación implica pares de permutaciones ; dicho par es suficiente para determinar un multigrafo , una superficie y una incrustación de 2 celdas del multigrafo en la superficie.
Cada esquema de rotación define una incrustación única de 2 celdas de un multigrafo conectado sobre una superficie orientada cerrada (hasta una equivalencia topológica que preserve la orientación). Por el contrario, cualquier incrustación de un multigrafo conectado G sobre una superficie cerrada orientada define un sistema de rotación único que tiene a G como su multigrafo subyacente. Esta equivalencia fundamental entre sistemas de rotación e incrustaciones de 2 celdas fue establecida por primera vez en una forma dual por Lothar Heffter en la década de 1890 [1] y fue ampliamente utilizada por Ringel durante la década de 1950. [2] Independientemente, Edmonds proporcionó la forma primaria del teorema [3] y los detalles de su estudio han sido popularizados por Youngs. [4] La generalización a multigrafos fue presentada por Gross y Alpert. [5]
Los sistemas de rotación están relacionados con los mapas de rotación utilizados por Reingold et al. (2002) para definir el producto en zigzag de los grafos, pero no son iguales . Un sistema de rotación especifica un ordenamiento circular de las aristas alrededor de cada vértice, mientras que un mapa de rotación especifica una permutación (no circular) de las aristas en cada vértice. Además, los sistemas de rotación se pueden definir para cualquier grafo, mientras que, como los definen Reingold et al., los mapas de rotación están restringidos a los grafos regulares .
Formalmente, un sistema de rotación se define como un par (σ, θ) donde σ y θ son permutaciones que actúan sobre el mismo conjunto fundamental B , θ es una involución libre de punto fijo y el grupo <σ, θ> generado por σ y θ actúa transitivamente sobre B .
Para derivar un sistema de rotación a partir de una incrustación de 2 celdas de un multigrafo conectado G sobre una superficie orientada, sea B el que consiste en los dardos (o banderas , o medias aristas ) de G ; es decir, para cada arista de G formamos dos elementos de B , uno para cada extremo de la arista. Incluso cuando una arista tiene el mismo vértice que sus dos extremos, creamos dos dardos para esa arista. Sea θ( b ) el otro dardo formado a partir de la misma arista que b ; esto es claramente una involución sin puntos fijos. Sea σ( b ) el dardo en la posición en el sentido de las agujas del reloj desde b en el orden cíclico de las aristas incidentes al mismo vértice, donde "en el sentido de las agujas del reloj" se define por la orientación de la superficie.
Si un multigrafo está incrustado en una superficie orientable pero no orientada, generalmente corresponde a dos sistemas de rotación, uno para cada una de las dos orientaciones de la superficie. Estos dos sistemas de rotación tienen la misma involución θ, pero la permutación σ para un sistema de rotación es la inversa de la permutación correspondiente para el otro sistema de rotación.
Para recuperar un multigrafo a partir de un sistema de rotación, formamos un vértice para cada órbita de σ y una arista para cada órbita de θ. Un vértice es incidente con una arista si estas dos órbitas tienen una intersección no vacía . Por lo tanto, el número de incidencias por vértice es el tamaño de la órbita y el número de incidencias por arista es exactamente dos. Si un sistema de rotación se deriva de una incrustación de 2 celdas de un multigrafo conectado G , el grafo derivado del sistema de rotación es isomorfo a G .
Para incrustar el grafo derivado de un sistema de rotación en una superficie, se forma un disco para cada órbita de σθ y se pegan dos discos a lo largo de una arista e siempre que los dos dardos correspondientes a e pertenezcan a las dos órbitas correspondientes a estos discos. El resultado es una incrustación de 2 celdas del multigrafo derivado, cuyas dos celdas son los discos correspondientes a las órbitas de σθ. La superficie de esta incrustación se puede orientar de tal manera que el ordenamiento en el sentido de las agujas del reloj de las aristas alrededor de cada vértice sea el mismo que el ordenamiento en el sentido de las agujas del reloj dado por σ.
De acuerdo con la fórmula de Euler podemos deducir el género g de la superficie orientable cerrada definida por el sistema de rotación (es decir, la superficie en la que el multigrafo subyacente está incrustado en 2 celdas). [6] Nótese que , y . Encontramos que
donde denota el conjunto de las órbitas de permutación .
