Escalera de Möbius

Escalera de Möbius
Dos vistas de la escalera de Möbius M16. Para ver una animación que muestra la transformación entre las dos vistas, consúltese este fichero
Nombre en honor a	August Möbius
Vértices	n (número par)
Aristas	n + n/2
Diámetro	1
Cintura	n/2 + 1
Número cromático	3
Índice cromático	3
Propiedades	Cúbico Circulante Vértices-transitivo Apical (para n > 4 par) Toroidal (para n > 4 par) Aristas-transitivo (para n= 4, 6) Bipartito (para n no doblemente par)
Notación	Mn

En teoría de grafos, la escalera de Möbius M_n, para números n pares, se forma a partir de un n-ciclo agregando aristas (llamadas "peldaños") que conectan pares opuestos de vértices en el ciclo. Es un grafo cúbico y circulante, llamado así porque, con la excepción de M₆ (el problema de los tres servicios K_3,3), M_n tiene exactamente n/2 4-ciclos,​ que se unen por sus aristas compartidas para formar una banda de Möbius topológica. Las escaleras de Möbius fueron nombradas y estudiadas por primera vez por Guy y Harary (1967).

Propiedades

Para cada n > 4 par, la escalera de Möbius M_n es un grafo de ápice no plano, lo que significa que no se puede dibujar sin cruces en el plano, pero al eliminar un vértice se puede dibujar el grafo restante sin cruces. Estos grafos tienen un número de cruces, pero se pueden incrustar sin cruces en un toro o en el plano proyectivo. Por lo tanto, son ejemplos de grafos toroidales.Li (2005) exploró las incrustaciones de estos grafos en superficies de género superior.

Las escaleras de Möbius son vértices-transitivas (tienen simetrías que llevan cualquier vértice a cualquier otro vértice), pero (con las excepciones de M₄ y M₆) no son isotoxales. Las aristas del ciclo a partir del cual se forma la escalera se pueden distinguir de los peldaños de la escalera, porque cada arista de ciclo pertenece a un solo 4-ciclo, mientras que cada peldaño pertenece a dos de estos ciclos. Por lo tanto, no hay simetría al llevar una arista de ciclo a una arista de peldaño o viceversa.

Cuando n = 2 (mod 4), M_n es bipartito. Cuando n = 0 (mod 4), no es bipartito. Los puntos finales de cada peldaño están separados por una distancia uniforme en el ciclo inicial, por lo que agregar cada peldaño crea un ciclo impar.

En este caso, debido a que el grafo es 3-regular pero no bipartito, por el teorema de Brooks se puede afirmar que posee coloración 3.De Mier y Noy (2004) demostró que las escaleras de Möbius están determinadas únicamente por sus polinomios de Tutte.

La escalera de Möbius M₈ tiene 392 árboles de expansión. Esta escalera y M₆ tienen la mayor cantidad de árboles de expansión entre todos los grafos cúbicos con el mismo número de vértices.​ Sin embargo, el grafo cúbico de 10 vértices con más árboles de expansión es el grafo de Petersen, que no es una escalera de Möbius.

Los polinomios de Tutte de las escaleras de Möbius pueden calcularse mediante una simple relación de recurrencia.​

Grafos menores

El grafo de Wagner M₈

Las escaleras de Möbius juegan un papel importante en la teoría de grafos menores. El primer resultado de este tipo es un teorema de Klaus Wagner (1937) según el que se pueden formar grafos sin el menor K₅ mediante el uso de operaciones de suma de cliques para combinar grafos planos y la escalera de Möbius M₈; por esta razón M₈ se llama grafo de Wagner.Gubser (1996) definió un grafo casi plano como un grafo no plano para el que todo menor no trivial es plano. También demostró que los grafos casi planos 3-conectados son escaleras de Möbius o miembros de un pequeño número de otras familias, y que se pueden formar otros grafos casi planos a partir de estos mediante una secuencia de operaciones simples.Maharry (2000) demostró que casi todos los grafos que no tienen un menor cúbico pueden generarse mediante una secuencia de operaciones simples sobre las escaleras de Möbius.

Química y física

Walba, Richards y Haltiwanger (1982) sintetizó por primera vez estructuras moleculares en forma de escalera de Möbius, y desde entonces esta estructura ha sido de interés en química y estereografía química,​ especialmente en vista de la forma de escalera de las moléculas de ADN. Con esta aplicación en mente,Erica Flapan (1989) estudió las simetrías matemáticas de los embebidos de las escaleras de Möbius en R³. En particular, como muestra, cada inserción tridimensional de una escalera de Möbius con un número impar de peldaños es topológicamente quiral: no puede convertirse en su imagen especular mediante una deformación continua del espacio sin pasar un borde por otro. Por otro lado, las escaleras de Möbius con un número par de peldaños tienen embebidos en R³ que pueden deformarse para obtener sus imágenes especulares.

Igualmente, se han utilizado como la forma de un anillo superconductor en experimentos para estudiar los efectos de la topología del conductor en las interacciones de los electrones.​

Optimización combinatoria

Las escaleras de Möbius también se han utilizado en ciencias de la computación, como parte de los enfoques de programación en enteros para problemas de empaquetamiento de conjuntos y ordenamiento lineal. Ciertas configuraciones dentro de estos problemas se pueden usar para definir facetas del politopo que describen una relajación en la programación lineal del problema; estas facetas se denominan restricciones de escalera de Möbius.​

Véase también

• Grafo de Ladder
• Grafo prisma

Bibliografía

• Biggs, N. L.; Damerell, R. M.; Sands, D. A. (1972). «Recursive families of graphs». Journal of Combinatorial Theory. Series B 12 (2): 123-131. MR 0294172. doi:10.1016/0095-8956(72)90016-0. 
• Bolotashvili, G.; Kovalev, M.; Girlich, E. (1999). «New facets of the linear ordering polytope». SIAM Journal on Discrete Mathematics 12 (3): 326-336. MR 1710240. doi:10.1137/S0895480196300145. «citeseerx: 10.1.1.41.8722». 
• Borndörfer, Ralf; Weismantel, Robert (2000). «Set packing relaxations of some integer programs». Mathematical Programming. Series A 88 (3): 425-450. MR 1782150. S2CID 206862305. doi:10.1007/PL00011381. 
• Deng, Wen-Ji; Xu, Ji-Huan; Liu, Ping (2002). «Period halving of persistent currents in mesoscopic Möbius ladders». Chinese Physics Letters 19 (7): 988-991. Bibcode:2002ChPhL..19..988D. S2CID 119421223. arXiv:cond-mat/0209421. doi:10.1088/0256-307X/19/7/333. 
• Flapan, Erica (1989). «Symmetries of Möbius ladders». Mathematische Annalen 283 (2): 271-283. MR 0980598. S2CID 119705062. doi:10.1007/BF01446435. 
• Grötschel, M.; Jünger, M.; Reinelt, G. (1985a). «On the acyclic subgraph polytope». Mathematical Programming 33: 28-42. MR 0809747. S2CID 206798683. doi:10.1007/BF01582009. 
• Grötschel, M.; Jünger, M.; Reinelt, G. (1985b). «Facets of the linear ordering polytope». Mathematical Programming 33: 43-60. MR 0809748. S2CID 21071064. doi:10.1007/BF01582010. 
• Gubser, Bradley S. (1996). «A characterization of almost-planar graphs». Combinatorics, Probability and Computing 5 (3): 227-245. MR 1411084. S2CID 7313209. doi:10.1017/S0963548300002005. 
• Guy, Richard K.; Harary, Frank (1967). «On the Möbius ladders». Canadian Mathematical Bulletin 10 (4): 493-496. MR 0224499. doi:10.4153/CMB-1967-046-4. 
• Jakobson, Dmitry; Rivin, Igor (1999). On some extremal problems in graph theory. arXiv:math.CO/9907050. 
• Li, De-ming (2005). «Genus distributions of Möbius ladders». Northeastern Mathematics Journal 21 (1): 70-80. MR 2124859. 
• Maharry, John (2000). «A characterization of graphs with no cube minor». Journal of Combinatorial Theory. Series B 80 (2): 179-201. MR 1794690. doi:10.1006/jctb.2000.1968. 
• McSorley, John P. (1998). «Counting structures in the Möbius ladder». Discrete Mathematics 184 (1–3): 137-164. MR 1609294. doi:10.1016/S0012-365X(97)00086-1. 
• De Mier, Anna; Noy, Marc (2004). «On graphs determined by their Tutte polynomials». Graphs and Combinatorics 20 (1): 105-119. MR 2048553. S2CID 46312268. doi:10.1007/s00373-003-0534-z. 
• Mila, Frédéric; Stafford, C. A.; Capponi, Sylvain (1998). «Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons». Physical Review B 57 (3): 1457-1460. Bibcode:1998PhRvB..57.1457M. S2CID 35931632. arXiv:cond-mat/9705119. doi:10.1103/PhysRevB.57.1457. 
• Newman, Alantha; Vempala, Santosh (2001). Fences are futile: on relaxations for the linear ordering problem. Lecture Notes in Computer Science 2081. Berlin: Springer-Verlag. pp. 333-347. MR 2041937. doi:10.1007/3-540-45535-3_26. Archivado desde el original el 2 de enero de 2004. Consultado el 8 de octubre de 2006. 
• Simon, Jonathan (1992). «Knots and chemistry». New scientific applications of geometry and topology (Baltimore, MD, 1992). Proceedings of Symposia in Applied Mathematics 45. Providence, RI: American Mathematical Society. pp. 97-130. MR 1196717. 
• Valdes, L. (1991). «Extremal properties of spanning trees in cubic graphs». Proceedings of the Twenty-Second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991). Congressus Numerantium 85. pp. 143-160. MR 1152127. 
• Wagner, K. (1937). «Über eine Eigenschaft der ebenen Komplexe». Mathematische Annalen 114: 570-590. MR 1513158. S2CID 123534907. doi:10.1007/BF01594196. 
• Walba, D.; Richards, R.; Haltiwanger, R. C. (1982). «Total synthesis of the first molecular Möbius strip». Journal of the American Chemical Society 104 (11): 3219-3221. doi:10.1021/ja00375a051. 

Enlaces externos

• Weisstein, Eric W. «Möbius Ladder». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q4307303
• Multimedia: Moebius ladders / Q4307303