Bicoloración de $\mathbb{N}^2$ evitando el conjunto de patrones, ¿la densidad límite máxima es racional?

Question

Consideremos una bicoloración de $\mathbb{N}^2$ (blanco y negro), donde deseamos maximizar el límite (limsup) de la densidad de cuadrados negros en $[n] \times [n]$ como $n \to \infty$ . En este caso, identificamos cada punto con un cuadrado de forma obvia.

Sin embargo, hemos especificado un conjunto finito de subpatrones negros que no están permitidos. Es decir, un patrón es un subconjunto de $[k]\times [k]$ y cualquier traslación de este subconjunto no se permite en la coloración como todos los cuadrados negros.

Por ejemplo, tal vez no permitamos dos casillas negras adyacentes. Entonces, una coloración en damero tiene una densidad límite $1/2$ .

Actualizado después de la respuesta

Q1: Para cualquier conjunto finito de patrones prohibidos, ¿la(s) coloración(es) que maximizan la densidad serán siempre periódicas? NO

Q2: ¿Existe un conjunto finito de patrones prohibidos, de manera que la densidad límite máxima sólo puede obtenerse mediante una coloración no periódica? SI

P2b: ¿Existe un conjunto finito de patrones prohibidos, tal que la densidad límite máxima sea un número irracional? Nótese que esto requiere un patrón no periódico.

Q3: ¿Existe una densidad límite que no es realizable, es decir, existe una secuencia de coloraciones, $c_1,c_2,\dots$ con densidad límite creciente, pero la densidad límite no es realizable por ninguna coloración?

Q4: Dado que esto parece estar estrechamente relacionado con los problemas de mosaico y los patrones de permutación, ¿podría ser que la pregunta "¿El conjunto $F$ permiten una coloración con densidad límite $\geq d$ ?" es indecidible? SI

Según la biyección con las baldosas Wang, donde todas las baldosas tienen la misma densidad. Decidir si un conjunto finito de baldosas de Wang, embaldosa el plano, es indecidible.

*Nota que para cada conjunto de patrones prohibidos, colorear todos los cuadrados de blanco es una coloración válida. *

Nota: Sólo consideramos un conjunto finito de patrones prohibidos en todas las preguntas.

Answer 1

Esta es una versión mejorada de la respuesta. La versión anterior (que respondía a Q1 y Q2) se guarda a continuación.

Ahora mostramos que Q2b es equivalente a la pregunta de si un conjunto finito de translación Las baldosas de Wang pueden tener una densidad irracional de ocurrencias de alguna baldosa en un mosaico del plano. Por un translación Por baldosas Wang entendemos las baldosas Wang que sólo pueden ser trasladadas pero no giradas ni reflejadas. (Por tanto, las baldosas Wang habituales son un caso parcial).

$\underline{\Rightarrow}$ . Supongamos que en nuestra pregunta puede aparecer una densidad de supremos irracional. Sea $M$ ser mayor que el diámetro de cualquier patrón de prohibición. Cortar la disposición óptima en $M\times M$ cuadrados, y llamar a $2M\times 2M$ cuadrado formado por cuatro cuadrados de este tipo a azulejo (para que las baldosas vecinas se superpongan en un $2M\times M$ , $M\times 2M$ o $M\times M$ rectángulo). Entonces, cualquier disposición de las baldosas conduce a una coloración válida si se cumplen las reglas obvias de cómo deben ser vecinas estas baldosas; estas reglas simplemente dicen qué dos baldosas pueden ser vecinas en qué dirección. Uno puede ver fácilmente que tales reglas pueden ser modeladas por baldosas Wnag traslacionales (si es necesario, puedo poner más detalles, pero espero que esto sea conocido). Por último, está claro que algunas de estas baldosas deben tener una densidad irracional, si la densidad total es irracional.

$\underline{\Leftarrow}$ . A la inversa, a cada sistema de baldosas Wang traslacionales en el que puede aparecer una baldosa con una densidad máxima irracional le ponemos en correspondencia el conjunto de patrones de la siguiente manera. Queremos construir un conjunto de patrones correspondiente.

En primer lugar, por una aplicación estándar del lema de Koenig, basta con encontrar cuadrados arbitrariamente grandes que puedan ser coloreados con la densidad suficientemente cercana a la irracional $d$ y que ninguna coloración tiene una densidad mayor que $d$ . Para demostrar esto último, utilizaremos la condición de las tejas de Wang.

Elija una $k$ mucho mayor que el tamaño máximo de un patrón, un $n$ mucho más grande que $k$ y un $N$ mucho más grande que $n$ . A cada patrón, biyectar algunos $n\times n$ cuadrado para que (i) cada cuadrado utilizado contenga $d$ o $d+1$ cuadrados negros, y contiene todas las celdas límite; (ii) este cuadrado contiene $d+1$ celdas negras si es de un tipo distinguido; (iii) cualesquiera dos casillas utilizadas difieren, incluso si borramos como máximo $k$ cuadrados negros de cada uno. Llama a los cuadrados correspondientes completa .

1. Prohibir cualquier $n\times n$ cuadrado que no es un subcuadrado de un cuadrado completo desplazado.

2. Para un $(N+n)\times (N+n)$ plaza uno de cuyos $n\times n$ esquinas contiene una celda negra, sólo su $(2n-1)\times (2n-1)$ Los cuadrados de las esquinas también pueden contener algo negro.

Estas restricciones hacen que las celdas negras se agrupen en clusters que encajan en $n\times n$ cuadrados, y tales agrupaciones están suficientemente separadas.

3. Por último, poner las restricciones a los vecinos $n\times n$ baldosas a distancia $N$ (lo que significa que la posición del segundo $n\times n$ cuadrado se obtiene a partir del de la primera mediante el desplazamiento por $N$ ). Es decir, prohibir algunos $n\times (n+N)% and $ (n+N)\Nveces n$ arreglos donde los cuadrados completos limítrofes son de tipos que no pueden ser vecinos de esta manera. (Recordemos que enumeramos todos los translación por lo que la rotación de una ficha Wang cambia su tipo)

FIN_DE_CONSTRUCCIÓN

Ahora, un mosaico aperiódico de Wang con una densidad máxima irracional posible de una baldosa disociada proporciona una disposición que queremos demostrar que es óptima. Sea $\alpha$ sea su densidad.

Considera un arreglo óptimo. Afirmamos que contiene cuadrados arbitrariamente grandes que se organizan como si correspondieran a alguna pieza lagre de un mosaico de Wang. Tomemos cualquier $ND\times ND$ cuadrado $Q$ où $D$ es grande, y $Q$ tiene una densidad de al menos $\alpha$ . Entonces, aunque sus racimos no estén dispuestos de forma tan regular, las restricciones que tenemos hacen que exista una gran subregión de $Q$ donde se disponen de forma regular, y la densidad sigue siendo grande. Esto es lo que necesitábamos (recordemos el lema de Koenig).

VERSION ANTIGUA. Parece que se puede codificar, por ejemplo, los azulejos de Wang mediante este tipo de restricciones. Por ejemplo, responde afirmativamente a Q2 (y a Q1 en su forma actual).

Proceda de la siguiente manera. Suponga que tiene $\leq n!$ tipos de traslación de yiles. Elija $N$ mucho más grande que $n$ .

1. Prohibir dos celdas negras en una fila o columna de un $n\times n$ cuadrado.

2. Diga que todas las celdas negras de un $N\times N$ cuadrado debe estar en algún $n\times n$ cuadrado.

Después, la densidad está limitada por $n/N^2$ y nos gustaría alcanzar este límite. Para ello, si queremos un arreglo periódico de tal densidad, cada $N\times N$ cuadrado debe contener exactamente $n$ celdas negras en un $n\times n$ cuadrado, todos en diferentes filas y columnas (decimos que tal $n\times n$ cuadrado es completa ). Biyectamos algunos de los cuadrados completos a los elementos de un conjunto elegido de fichas Wang y prohibimos el resto.

3. Cuenta que en un $(n+N)\times (n+N)$ cuadrado, si uno $n\times n$ esquina contiene $n$ células, entonces sólo las otras esquinas de tamaño $n\times n$ puede contener celdas negras.

Esto demuestra que las posiciones de los cuadrados completos en un arreglo periódico forman una red generada por $(0,N)$ y $(N,0)$ .

4. Por último, imponga las restricciones a las fichas vecinas como desee. Es decir, prohíbe algunas $n\times (n+N)$ y $(n+N)\times n$ arreglos donde los cuadrados completos limítrofes son de tipos que no pueden ser vecinos de esta manera. (Recordemos que enumeramos todos los translación por lo que la rotación de una ficha Wang cambia su tipo)

Ahora bien, como sabemos que existe un conjunto de baldosas de Wang que sólo admite tilings no periódicos, esto demuestra que el arreglo de máxima densidad puede ser efectivamente aperiódico.

Answer 2

Creo que la respuesta a Q2b es sí, existen configuraciones en las que la densidad límite es irracional.

Consideremos los tilings de Kari-Culik (Wang), y dejemos que $\Phi$ sea la proyección sobre la etiqueta superior de cada baldosa (tratando $0'$ como $0$ ). Durand, Gamard y Grandjean en http://arxiv.org/abs/1312.4126 demuestran que para cualquier mosaico de Kari-Culik $x$ los promedios de las filas de $\Phi(x)$ convergen. Además, si $(\gamma_i)_{i\in\mathbb Z}$ es un vector de medias de filas,

$\gamma_i=f(\gamma_{i-1})$ donde $f(t) = \begin{cases}2t&t\in[1/3,1)\\ t/3 & t\in[1,2]\end{cases}$ .

$f$ es conjugado a una rotación irracional a través del mapa $\varphi:[1/3,2]\to [0,1]$ dado por $\varphi(t) = \frac{\log t+\log 3}{\log 6}$ y, por lo tanto, como una rotación irracional da una densidad orbital uniforme, empujando hacia adelante a través de $\varphi$ podemos calcular la media

$\mathrm{Ave}(\Phi(x)) = \frac{5}{\log 216}$

para cualquier mosaico de Kari-Culik $x$ . No he pensado en la correspondencia de los tilings de Wang y tu problema en detalle, pero después de traducir los tilings de Kari-Culik en el marco de tu bicolor, debería conservarse una media irracional.

Answer 3

Se puede dar una respuesta negativa a la P3 básicamente por la compacidad. Este es un argumento estándar en la "optimización ergódica". De hecho se puede hacer algo mejor de lo que pides. Se puede conseguir la máxima densidad no sólo en un $\limsup$ sentido, sino en realidad en un sentido límite. Es decir, si $\rho$ es el máximo $\limsup$ densidad, se puede producir un punto en el que para cada $\epsilon>0$ Hay un $N$ tal que cada $N\times N$ bloque tiene una densidad de al menos $\rho-\epsilon$ . En particular, la densidad (límite) de la configuración es $\rho$ .

Prueba: Sea $F$ sea la colección de configuraciones prohibidas todo-uno y supongamos que éstas tienen un diámetro máximo $K$ . Sea $\xi_N$ sea una configuración legal en $[1,N]^2$ con el máximo número de 1's. Sea $\rho_N$ sea la densidad de 1's en $\xi_N$ (el número de 1's dividido por $N^2$ ). Sea $\xi$ sea cualquier punto límite de estas configuraciones.

Reclamación 1: $\rho_N$ es una secuencia convergente.

Prueba: Para $0\le k<N$ tenemos $(mN+k)^2\rho_{mN+k}\le (m+1)^2\rho_N N^2$ como si no, $\xi_{mN+k}$ contiene un $N\times N$ subregión con una densidad superior a $\rho_N$ . Por lo tanto, obtenemos $\rho_{mN+k}\le (m+1)^2/m^2\rho_N$ para que $\limsup\rho_n\le \rho_N$ . Por lo tanto, $\lim\rho_n=\inf\rho_n$ .

Ahora dejemos que $\epsilon>0$ . Sea $N$ sea tal que $(N+2K)^2/N^2<1+\epsilon$ .

Reclamación 2: La restricción de $\xi$ a cualquier $N\times N$ subregión tiene una densidad de al menos $\rho-\epsilon$ de 1's.

Prueba: Supongamos que no. Supongamos que la restricción de $\xi$ a un $N\times N$ subregión $R$ tiene una densidad inferior a $\rho-\epsilon$ . Entonces, como $\xi$ es el límite de una sucesión de $\xi_n$ Hay un $\xi_n$ , de manera que la restricción de $\xi_n$ à $R$ coincide con $\xi$ . Ahora modificamos $\xi_n$ : borrar el $(N+2K)\times (N+2K)$ región que rodea $R$ y pegar una copia de $\xi_N$ en el centro para producir $\tilde\xi_n$ . Esta es una configuración legal. El número de 1's que se han eliminado es como máximo $(\rho-\epsilon)N^2+((N+2K)^2-N^2)<\rho N^2$ . El número de 1's que se han añadido es $\rho_N N^2\ge \rho N^2$ . Por lo tanto, $\tilde\xi_n$ tiene mayor densidad que $\xi_n$ . Esto es una contradicción.