En geometría , un mosaico de dominó de una región en el plano euclidiano es un mosaico de la región mediante dominós , formas formadas por la unión de dos cuadrados unitarios que se encuentran de borde a borde. De manera equivalente, es una coincidencia perfecta en el gráfico de cuadrícula formado al colocar un vértice en el centro de cada cuadrado de la región y conectar dos vértices cuando corresponden a cuadrados adyacentes.
Funciones de altura
Para algunas clases de mosaicos en una cuadrícula regular en dos dimensiones, es posible definir una función de altura asociando un número entero a los vértices de la cuadrícula. Por ejemplo, dibuja un tablero de ajedrez, arregla un nodo con altura 0, entonces para cualquier nodo hay una ruta desde lo. En este camino defina la altura de cada nodo (es decir, esquinas de los cuadrados) para ser la altura del nodo anterior más uno si el cuadrado a la derecha del camino de a es negro y menos uno en caso contrario.
Se pueden encontrar más detalles en Kenyon y Okounkov (2005) .
Condición de altura de Thurston
William Thurston (1990) describe una prueba para determinar si una región simplemente conectada, formada como la unión de cuadrados unitarios en el plano, tiene un mosaico de dominó. Forma un gráfico no dirigido que tiene como vértices los puntos ( x , y , z ) en la red de enteros tridimensionales , donde cada uno de esos puntos está conectado a cuatro vecinos: si x + y es par, entonces ( x , y , z ) está conectado a ( x + 1, y , z + 1), ( x - 1, y , z + 1), ( x , y + 1, z - 1) y ( x , y - 1, z - 1), mientras que si x + y es impar, entonces ( x , y , z ) está conectado a ( x + 1, y , z - 1), ( x - 1, y , z - 1), ( x , y + 1, z + 1) y ( x , y - 1, z + 1). El límite de la región, visto como una secuencia de puntos enteros en el plano ( x , y ), se eleva de forma única (una vez que se elige una altura inicial) a una ruta en este gráfico tridimensional . Una condición necesaria para que esta región sea enlosable es que este camino debe cerrarse para formar una curva cerrada simple en tres dimensiones, sin embargo, esta condición no es suficiente. Utilizando un análisis más cuidadoso de la trayectoria del límite, Thurston dio un criterio para la capacidad de mosaico de una región que era tanto suficiente como necesario.
Contando mosaicos de regiones
El número de formas de cubrir un rectángulo con dominó, calculado independientemente por Temperley y Fisher (1961) y Kasteleyn (1961) , está dado por
Cuando ambos m y n son impares, la fórmula se reduce a cero correctamente posibles embaldosados dominó.
Se produce un caso especial al colocar en mosaico rectángulo con n dominós: la secuencia se reduce a la secuencia de Fibonacci (secuencia A000045 en la OEIS ) ( Klarner & Pollack 1980 ) .
Otro caso especial ocurre para cuadrados con m = n = 0, 2, 4, 6, 8, 10, 12, ... es
Estos números se pueden encontrar escribiéndolos como el Pfaffian de un matriz de simetría sesgada cuyos valores propios se pueden encontrar explícitamente. Esta técnica se puede aplicar en muchas materias relacionadas con las matemáticas, por ejemplo, en el cálculo bidimensional clásico de la función correladora dímero-dímero en mecánica estadística .
El número de teselaciones de una región es muy sensible a las condiciones de los límites y puede cambiar drásticamente con cambios aparentemente insignificantes en la forma de la región. Esto se ilustra con el número de mosaicos de un diamante azteca de orden n , donde el número de mosaicos es 2 ( n + 1) n / 2 . Si esto se reemplaza por el "diamante azteca aumentado" de orden n con 3 filas largas en el medio en lugar de 2, el número de teselaciones cae al número mucho más pequeño D ( n , n ), un número de Delannoy , que solo tiene valores exponenciales. en lugar de un crecimiento superexponencial en n . Para el "diamante azteca reducido" de orden n con solo una fila central larga, solo hay un mosaico.
Un diamante azteca de orden 4, que tiene 1024 mosaicos de dominó.
Un posible mosaico
Tatami
Los tatami son alfombrillas japonesas en forma de dominó (rectángulo de 1x2). Se utilizan para colocar azulejos en las habitaciones, pero con reglas adicionales sobre cómo se pueden colocar. En particular, por lo general, los cruces donde se encuentran tres tatami se consideran propicios, mientras que los cruces donde se juntan cuatro son desfavorables, por lo que un mosaico de tatami adecuado es uno en el que solo tres tatami se encuentran en cualquier esquina ( Mathar 2013 ; Ruskey & Woodcock 2009 ). El problema de embaldosar una habitación irregular con tatami que se juntan tres en una esquina es NP-completo ( Erickson & Ruskey 2013 ).
Curvas de relleno de espacio degeneradas
Cualquier conjunto finito de celdas que formen una cuadrícula cuadrada regular n × n puede indexarse mediante una curva de relleno de espacio seleccionada que sea consistente con cuadrados (que hacen una recursividad de cuatro particiones de la cuadrícula de unidades cuadriláteras), con un índice i que va de 0 a n 2 -1. Geométricamente, la curva se puede dibujar como un camino a través del centro de las celdas cuadradas. Un mosaico de dominó se obtiene fusionando las celdas vecinas. El índice j de cada dominó se obtendrá mediante la función j = piso ( i ÷ 2) del índice de la cuadrícula original. La nueva curva fractal es una "curva degenerada" porque es otro fractal. Ejemplos:
La " curva de relleno de espacio de Morton degenerada " produce un mosaico dominó de orientación horizontal regular; la curva está relacionada con la indexación de Geohash , donde la curva en forma de Z se transforma en una curva en forma de И.
La " curva de llenado de espacio de Hilbert degenerada " produce un sistema de mosaico aperiódico , que mezcla dominós de orientación horizontal y vertical, el 50% de cada orientación. La curva de Hilbert degenerada es isomorfa al fractal de Munkres. [1]
Aplicaciones en física estadística
Existe una correspondencia uno a uno entre un mosaico de dominó periódico y una configuración de estado fundamental del modelo de Ising completamente frustrado en una red periódica bidimensional. [2] Para ver eso, observamos que en el estado fundamental, cada placa del modelo de giro debe contener exactamente una interacción frustrada . Por lo tanto, visto desde la celosía dual , cada borde frustrado debe estar "cubierto" por un rectángulo de 1x2 , de modo que los rectángulos abarquen toda la celosía y no se superpongan, o un mosaico dominó de la celosía dual.
Ver también
- Campo libre gaussiano , el límite de escala de la función de altura en la situación genérica (por ejemplo, dentro del disco inscrito de un gran diamante azteca)
- Problema de tablero de ajedrez mutilado , un rompecabezas sobre el mosaico de dominó de un subconjunto de 62 cuadrados del tablero de ajedrez
- Mecánica estadística
Referencias
- ^ El fractal de Munkres se define en "Teorema 44.1" en faculty.etsu.edu/gardnerr/5357/notes/Munkres-44
- ↑ Barahona, F (1 de octubre de 1982). "Sobre la complejidad computacional de los modelos de vidrio giratorio de Ising" . Revista de Física A: Matemática y General . 15 (10): 3241–3253. Código Bibliográfico : 1982JPhA ... 15.3241B . doi : 10.1088 / 0305-4470 / 15/10/028 . ISSN 0305-4470 .
- Bodini, Olivier; Latapy, Matthieu (2003), "Generalizado Tilings con funciones Altura" (PDF) , morfismos , 7 (1): 47-68, ISSN 1870-6525 , Archivado desde el original, el 2012-02-10 , recuperada 2008-09- 08CS1 maint: URL no apta ( enlace )
- Erickson, Alejandro; Ruskey, Frank (2013), "La cobertura de tatami de Domino es NP-completo", Algoritmos combinatorios , Lecture Notes in Comput. Sci., 8288 , Springer, Heidelberg, págs. 140-149, arXiv : 1305.6669 , doi : 10.1007 / 978-3-642-45278-9_13 , MR 3162068 , S2CID 12738241
- Faase, F. (1998), "Sobre el número de subgráficos de expansión específicos de los gráficos GX P_n", Ars Combin. , 49 : 129-154, MR 1633083
- Hock, JL; McQuistan, RB (1984), "Una nota sobre la degeneración ocupacional de los dímeros en un espacio reticular bidimensional saturado", Discrete Applied Mathematics , 8 : 101-104, doi : 10.1016 / 0166-218X (84) 90083-0 , Señor 0739603
- Kasteleyn, PW (1961), "Las estadísticas de dímeros en una celosía. I. El número de arreglos de dímeros en una celosía cuadrática", Physica , 27 (12): 1209-1225, Bibcode : 1961Phy .... 27.1209K , doi : 10.1016 / 0031-8914 (61) 90063-5
- Kenyon, Richard (2000), "El modelo de dímero plano con límite: una encuesta", en Baake, Michael; Moody, Robert V. (eds.), Direcciones en cuasicristales matemáticos , CRM Monograph Series, 13 , Providence, RI: American Mathematical Society , págs. 307–328, ISBN 0-8218-2629-8, MR 1798998 , Zbl 1026.82007
- Kenyon, Richard; Okounkov, Andrei (2005), "¿Qué es ... un dímero?" (PDF) , Notices of the American Mathematical Society , 52 (3): 342–343, ISSN 0002-9920
- Klarner, David ; Pollack, Jordan (1980), "Azulejos dominó de rectángulos con ancho fijo", Matemáticas discretas , 32 (1): 45–52, doi : 10.1016 / 0012-365X (80) 90098-9 , MR 0588907 , Zbl 0444.05009
- Mathar, Richard J. (2013), Pavimentación de regiones rectangulares con baldosas rectangulares: revestimientos de tatami y no tatami , arXiv : 1311.6135 , Bibcode : 2013arXiv1311.6135M
- Propp, James (2005), "Lambda-determinants and dominó-tilings", Advances in Applied Mathematics , 34 (4): 871–879, arXiv : math.CO/0406301 , doi : 10.1016 / j.aam.2004.06.005 , S2CID 15679557
- Ruskey, Frank ; Woodcock, Jennifer (2009), "Contando tejas de tatami de altura fija" , Electronic Journal of Combinatorics , 16 (1): R126, doi : 10.37236 / 215 , MR 2558263
- Sellers, James A. (2002), "Dominó y productos de números de Fibonacci y Pell" , Journal of Integer Sequences , 5 (Artículo 02.1.2): 12, Bibcode : 2002JIntS ... 5 ... 12S
- Stanley, Richard P. (1985), "Sobre revestimientos dímeros de rectángulos de ancho fijo", Matemáticas aplicadas discretas , 12 : 81–87, doi : 10.1016 / 0166-218x (85) 90042-3 , MR 0798013
- Thurston, WP (1990), "Conway's Tiling Groups ", American Mathematical Monthly , Mathematical Association of America, 97 (8): 757–773, doi : 10.2307 / 2324578 , JSTOR 2324578
- Wells, David (1997), The Penguin Dictionary of Curious and Interesting Numbers (edición revisada), Londres: Penguin, p. 182, ISBN 0-14-026149-4
- Temperley, HNV ; Fisher, Michael E. (1961), "Problema de dímero en mecánica estadística - un resultado exacto", Philosophical Magazine , 6 (68): 1061–1063, Bibcode : 1961PMag .... 6.1061T , doi : 10.1080 / 14786436108243366