Sistema de rotación

En matemáticas combinatorias, un sistema de rotación (también llamado incrustación o embebido combinatorio) sirve para codificar grafos embebidos en superficies orientables, describiendo la ordenación circular de los bordes de un grafo alrededor de cada vértice.

Una definición más formal de un sistema de rotación implica pares de permutaciones. Dichos pares son suficientes para determinar un multigrafo, una superficie y un embebido de dos celdas del multigrafo sobre la superficie.

Cada esquema de rotación define una incrustación única de dos celdas de un multigrafo connectado en una superficie orientada cerrada (hasta la equivalencia topológica que conserva la orientación). Por el contrario, cualquier incrustación de un multigrafo conectado G en una superficie cerrada orientada define un sistema de rotación único que tiene G como su multigrafo subyacente. Esta equivalencia fundamental entre los sistemas de rotación y los embebidos de dos celdas fue establecida por primera vez de forma dual por Lothar Heffter en la década de 1890​ y utilizada ampliamente por Ringel durante la década de 1950.​ Independientemente, Edmonds dio la forma original del teorema​ y los detalles de su estudio han sido popularizados por Youngs.​ La generalización a multigrafos fue presentada por Gross y Alpert.​

Los sistemas de rotación están relacionados, pero no son los mismos, con los mapas de roración utilizados por Reingold et al. (2002) para definir el producto en zig-zag de grafos. Un sistema de rotación especifica una ordenación 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 grafo, mientras que los mapas de rotación definidos según Reingold et al. están restringidos a grafos regulares.

Definición formal

Formalmente, un sistema de rotación se define como un par (σ, θ) donde σ y θ son permutaciones que actúan sobre el mismo conjunto base B, θ es un punto fijo libre de involución, y el grupo <σ,  θ> generado por las acciones σ y θ transitivamente en B.

Para deducir un sistema de rotación de un embebido de 2 celdas de un multigrafo conectado G en una superficie orientada, B debe consistir en los dardos (o banderas, o semiaristas) de G; es decir, para cada arista de G se deben formar dos elementos de B, uno para cada extremo de la arista. Incluso cuando una arista tiene el mismo vértice que sus dos extremos, se crean dos dardos para esa arista. Sea θ(b) el otro dardo formado por la misma arista que b; esto es claramente una involución sin puntos fijos. Ahora sea σ(b) el dardo en la posición de las agujas del reloj desde b en el orden cíclico de las aristas que inciden en el mismo vértice, donde «las agujas del reloj» se definen 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.

Recuperación del embebido del sistema de rotación

Para recuperar un multigrafo de un sistema de rotación, se dispone de 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. Así, 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 un embebido de dos celdas de un multigrafo conectado G, el gráfico derivado del sistema de rotación es isomórfico a G.

Para embeber el gráfico derivado de un sistema de rotación en una superficie, se debe formar un disco para cada órbita de σθ y pegar dos discos en un borde e siempre que los dos dardos correspondientes a e pertenezcan a las dos órbitas correspondientes a estos discos. El resultado es un embebido de dos celdas del multigrafo derivado, cuyas dos celdas son los discos correspondientes a las órbitas de σθ. La superficie de este embebido se puede orientar de tal manera que el orden en el sentido de las agujas del reloj de los bordes alrededor de cada vértice sea el mismo que el orden en el sentido de las agujas del reloj dado por σ.

Caracterización de la superficie del embebido

De acuerdo con la fórmula de Euler, es posible deducir el genus g de la superficie cerrada orientable definida por el sistema de rotación $(\sigma ,\theta )$ (es decir, la superficie en la que el multigrafo subyacente es un embebido de 2 celdas).​ Observe que $V=|Z(\sigma )|$, $E=|Z(\theta )|$ y $F=|Z(\sigma \theta )|$. En consecuencia

$g=1-{\frac {1}{2}}(V-E+F)=1-{\frac {1}{2}}(|Z(\sigma )|-|Z(\theta )|+|Z(\sigma \theta )|)$

donde $Z(\phi )$ denota el conjunto de las órbitas de permutación $\phi$.

Véase también

• Aplicación combinatoria

Bibliografía

• R. Cori; A. Machì (1992). «Maps, hypermaps and their automorphisms: a survey». Expositiones Mathematicae 10: 403-467. MR 1190182. 
• J. Edmonds (1960). «A combinatorial representation for polyhedral surfaces». Notices of the American Mathematical Society 7: 646. 
• Edmonds, John Robert (1960). A combinatorial representation for oriented polyhedral surfaces (Masters). University of Maryland. 
• J. L. Gross; S. R. Alpert (1974). «The topological theory of current graphs». Journal of Combinatorial Theory, Series B 17 (3): 218-233. MR 0363971. doi:10.1016/0095-8956(74)90028-8. 
• L. Heffter (1891). «Über das Problem der Nachbargebiete». Mathematische Annalen 38 (4): 477-508. S2CID 121206491. doi:10.1007/BF01203357. 
• L. Heffter (1898). «Über metacyklische Gruppen und Nachbarcontigurationen». Mathematische Annalen 50 (2–3): 261-268. S2CID 120691296. doi:10.1007/BF01448067. 
• Lando, Sergei K.; Zvonkin, Alexander K. (2004). Graphs on Surfaces and Their Applications. Encyclopaedia of Mathematical Sciences: Lower-Dimensional Topology II 141. Berlin, New York: Springer Science+Business Media. ISBN 978-3-540-00203-1. .
• Bojan Mohar and Carsten Thomassen (2001). Graphs on Surfaces. The Johns Hopkins University Press. ISBN 0-8018-6689-8. 
• O. Reingold; S. Vadhan; A. Wigderson (2002). «Entropy waves, the zig-zag graph product, and new constant-degree expanders». Annals of Mathematics 155 (1): 157-187. JSTOR 3062153. MR 1888797. S2CID 120739405. arXiv:math/0406038. doi:10.2307/3062153. 
• G. Ringel (1965). «Das Geschlecht des vollständigen paaren Graphen». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 28 (3–4): 139-150. MR 0189012. S2CID 120414651. doi:10.1007/BF02993245. 
• J. W. T. Youngs (1963). «Minimal imbeddings and the genus of a graph». Journal of Mathematics and Mechanics 12 (2): 303-315. MR 0145512. doi:10.1512/iumj.1963.12.12021. 

• Datos: Q7370316