En matemática combinatoria , los sistemas de rotación (también llamados incrustaciones combinatorias ) codifican incrustaciones de gráficos en superficies orientables al describir el orden circular de los bordes de un gráfico alrededor de cada vértice. Una definición más formal de un sistema de rotación implica pares de permutaciones; tal par es suficiente para determinar un multigraph, una superficie y una incrustación de 2 celdas del multigraph en la superficie.
Cada esquema de rotación define una incrustación única de 2 celdas de un multigraph conectado en una superficie orientada cerrada (hasta la equivalencia topológica que preserva la orientación). A la inversa, cualquier incrustación de un multigraph G conectado en una superficie cerrada orientada define un sistema de rotación único que tiene G como su multigraph subyacente. Esta equivalencia fundamental entre los sistemas de rotación y las incrustaciones de 2 celdas fue establecida por primera vez en una forma dual por Lothar Heffter en la década de 1890 [1] y ampliamente utilizada por Ringel durante la década de 1950. [2] Independientemente, Edmonds dio la forma primaria del teorema [3] y Youngs popularizó los detalles de su estudio. [4] Gross y Alpert presentaron la generalización a multigrafías. [5]
Los sistemas de rotación están relacionados, pero no son los mismos que, los mapas de rotación utilizados por Reingold et al. (2002) para definir el producto en zig-zag de los gráficos. Un sistema de rotación especifica un orden circular de los bordes alrededor de cada vértice, mientras que un mapa de rotación especifica una permutación (no circular) de los bordes en cada vértice. Además, los sistemas de rotación se pueden definir para cualquier gráfico, mientras que Reingold et al. definirlos mapas de rotación están restringidos a gráficos regulares .
Formalmente, un sistema de rotación se define como un par (σ, θ) donde σ y θ son permutaciones que actúan sobre el mismo conjunto básico B , θ es una involución libre de punto fijo y el grupo <σ, θ> generado por σ y θ actúa transitivamente en B .
Para derivar un sistema de rotación a partir de una incrustación de 2 celdas de un multigraph G conectado en una superficie orientada, supongamos que B consiste en los dardos (o banderas , o medios bordes ) de G ; es decir, para cada borde de G formamos dos elementos de B , uno para cada punto final del borde. Incluso cuando un borde tiene el mismo vértice que sus dos extremos, creamos dos dardos para ese borde. Dejamos que θ ( b ) sea el otro dardo formado por el mismo borde que b ; esta es claramente una involución sin puntos fijos. Dejamos que σ ( b ) sea el dardo en el sentido de las agujas del reloj desde b en el orden cíclico de los bordes 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 multigraph 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.