Los tatami tilings de Monómero-Dímero necesitan mejores relaciones con otras matemáticas. Resumen de los resultados

Question

Un mosaico monómero-dímero de una rejilla rectangular con $r$ filas y $c$ columnas satisface la tatami si no se juntan cuatro fichas en ningún punto. (O se puede pensar en ello como la eliminación de un emparejamiento de un gráfico de cuadrícula que rompe todos los $4$ -ciclos).

Esta simple restricción, sobre la que Don Knuth me llamó la atención en el Vol 4 de TAOCP, se convirtió en el tema de mi tesis doctoral, cuando mi grupo de investigación y yo descubrimos que impone una estructura estéticamente agradable con una bonita descripción, y abrió un montón de preguntas divertidas.

Aquí está mi ejemplo favorito, que tiene todas las "características" posibles. Primero se muestra sin colorear

     (fuente)

Y aquí está coloreado

     (fuente)

Los azulejos magenta muestran los tipos de características que puede tener, y aquí están solos:

     (fuente)

     (fuente)

Presentaré aquí mi pregunta y resumiré algunos resultados más adelante. Quiero encontrar más y mejores vínculos entre los tatami tilings y otros problemas matemáticos menos esotéricos. Si se te ocurre algún artículo o tema que pueda interesarme, no dudes en responderme.

En nuestro primer documento probamos la estructura anterior y demostramos que:

1. Un mosaico se describe mediante los mosaicos de su contorno y, por tanto, tiene una descripción lineal en las dimensiones de la malla.
2. El número máximo de monómeros es como máximo max(r+1,c+1), y esto es alcanzable.
3. Encontramos un algoritmo para encontrar el polinomio racional generador de los números de tilings de altura r (que creo que también se puede calcular con el método de la matriz de transferencia).

Planteamos un par de cuestiones de complejidad (en las que estoy trabajando), por ejemplo, ¿es NP-difícil reconstruir un mosaico de tatami dadas sus proyecciones de filas y columnas?

     (fuente)

¿O embaldosar una región ortogonal dada sin monómeros?

     (fuente)

A continuación nos centramos en enumeración de tilings de la $n\times n$ cuadrícula y encontró una partición de $n\times n$ baldosas con el máximo número de monómeros en $n$ partes de tamaño $2^{n-1}$ . También contamos el número de tilings con $k$ monómeros, y esta curiosa consecuencia:

El número de $n \times n$ tatami es igual a la suma de los cuadrados de todas las partes en todas las composiciones de $n$ . Es decir, $2^{n-1}(3n-4)+2$ .

También encontramos un algoritmo para generar las que tienen $n$ monómeros, y una especie de código Gray.

Bonitos números y un bonito problema, pero otro artículo que se contiene en sí mismo con un razonamiento elemental (aunque algo complicado).

Nuestro tercer artículo en esta historia (en preparación), examina el polinomio generador de $n\times n$ tilings con $n$ monómeros cuyos coeficientes son el número de tilings con exactamente $v$ dímeros verticales (o $h$ dímeros horizontales). Resulta que este polinomio generador es un producto de polinomios ciclotómicos, y un polinomio algo misterioso y aparentemente irreducible, cuyas raíces complejas tienen este aspecto:

     (fuente)

Hemos encontrado un montón de cosas interesantes al respecto, por ejemplo la evaluación de este polinomio en $-1$ es $\binom{2n}{n}$ para $2(n+1)\times 2(n+1)$ y encontramos que nuestro polinomio generador da un algoritmo para generar los tilings en tiempo amortizado constante. He aquí algunos resultados de la aplicación:

    $8\times 8$ tilings con $8$ monómeros y $7$ dímeros verticales". /> (fuente)

Esa es la mayor parte de la historia publicada (y casi publicada). Hay una conexión suelta con otros problemas monómero-dímero, y cosas que puedo investigar, como los tatamis aztecas, pero Estoy buscando aplicaciones directas de otros resultados a estos, o viceversa, especialmente con este último trabajo en preparación. No te pido que investigues por mí, sino tus ideas tal y como están ahora, para que pueda ir aprendiendo cosas nuevas.

No dude en comentar lo que le parezca interesante, o no, sobre los tatamis.

Answer 1

Los tilings en relación con la indecidibilidad han estado en MO antes, (ver Wang tiles). Tal vez, si nos fijamos en las regiones no limitadas, ¿pueden ser indecidibles algunas cuestiones sobre la teselabilidad?