Cada punto de una cuadrícula se colorea en azul, rojo o verde. Cómo demostrar que existe un rectángulo monocromático?

Question

Tengo un $3$ -coloración de $\mathbb{Z}\times\mathbb{Z}$ es decir, una función $f:\mathbb{Z}\times\mathbb{Z}\to\{\color{red}{\text{red}},\color{green}{\text{green}},\color{blue}{\text{blue}}\}$ .

Tengo que demostrar que existe un rectángulo monocromático cuyos lados son paralelos al eje, es decir, demostrar que para alguna elección de $a,b,c,d\in\mathbb{Z}$ con $a\neq b$ y $c\neq d$ todos los puntos $(a,c),(a,d),(b,c),(b,d)\,$ tienen el mismo color.

Intenté trabajar por contradicción, sin conseguir gran cosa.

Además, ¿podemos demostrar algún límite superior para $|a-b|$ y $|c-d|$ ?

Answer 1

Dicho rectángulo se producirá en una cuadrícula de $19$ columnas de $4$ filas.

Por el principio de encasillamiento, cada columna debe tener un punto de color repetido. Ignorando cualquier repetición posterior, clasifique las columnas según las dos primeras posiciones de color repetidas; hay $6$ opciones: $(1,2), (1,3), (1,4), (2, 3), (2, 4)$ y $(3,4)$ . Así que como también hay $3$ opciones de color para los colores repetidos sólo hay $6\times3=18$ diferentes opciones de color repetido por posición. Por lo tanto, por el principio de casillero de nuevo, en un $19\times 4$ debemos tener un rectángulo adecuado con las esquinas del mismo color.

---

A partir de una observación de Pere en los comentarios:

Para $n$ colores, utilizando el mismo enfoque, adoptaríamos una cuadrícula de $(n+1)$ filas y, a continuación, exigir $n{n+1 \choose 2}+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columnas para encontrar un rectángulo con esquinas del mismo color.

Answer 2

Para una prueba un poco más cuantitativa, podemos demostrar que existe un rectángulo monocromático cuya mayor dimensión es $\color{red}{\leq 82}$ y su dimensión más pequeña es $\color{red}{\leq 4}$ .

Paso 1. Podemos dar a cualquier punto entero $(x,0)$ en el $x$ -eje un maxi-color en el conjunto $\{1,2,\ldots,80,81\}$ dependiendo de los colores reales de $(x,0),(x,1),(x,2),(x,3)$ .

Segundo paso. Por el principio de la caja de Dirichlet, entre $82$ puntos reticulares consecutivos en el $x$ -eje al menos dos de ellos, digamos $(a,0)$ y $(b,0)$ tienen el mismo color máximo.

Tercer paso. Dado que sólo tenemos tres colores reales, al menos dos puntos entre $(a,0),(a,1),(a,2),(a,3)$ tienen el mismo color. Dichos puntos, junto con los puntos correspondientes en $x=b$ se obtiene el rectángulo monocromático deseado.

---

Le site $82$ anterior puede sustituirse por un número menor, a saber $1+\alpha(G)$ es decir, uno más el tamaño del mayor conjunto independiente en un grafo bastante complicado (del tipo Haggkvist-Hell tipo) en $81$ vértices. Así que también podemos mejorar el límite dado utilizando algunos resultados bastante profundos sobre grafos topológicos (véase Conjetura de Kneser demostrado por Lovasz en 1978 mediante la Teorema de Borsuk-Ulam ).

Sin embargo, una prueba elemental de que $\alpha(G)=18$ se presenta más arriba por Joffan.

Answer 3

Teorema: Sea $X,Y$ sean conjuntos infinitos. Si los puntos de $X\times Y$ se colorean con un número finito de colores de tal forma que existe un conjunto $C$ de $c$ colores tales que para cada $x\in X$ sólo colores en $C$ aparecen un número infinito de veces entre pares de la forma $(x,y)$ entonces existe $x_1,x_2\in X,y_1,y_2\in Y$ para que $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ todos tienen el mismo color.

Prueba:

Procedemos por inducción en $c$ cuando $c=1$ está claro. Tome cualquier $x_1,x_2$ y que $\alpha$ ser el único color que aparece un número infinito de veces. Observe que el conjunto de $A_{x_1}=\{y\in Y | (x_1,y) \text{ has color } \alpha\}$ tiene complemento finito, y también lo tiene el conjunto $A_{x_2}=\{y\in Y | (x_2,y) \text{ has color } \alpha\}$ . Esto implica $A_{x_1}\cap A_{x_2}$ es infinito. Tomando $x1,x2$ y cualquier $y_1,y_2\in A_{x_1}\cap A_{x_2}$ hace el truco.

Paso inductivo: Considere cualquier $x\in X$ debe haber un $\alpha \in Y$ tal que el conjunto $A_{x}=\{y\in Y | (x,y) \text{ has color } \alpha\}$ es infinita. Consideremos ahora el conjunto $X'=X\setminus x$ y $Y'=A_x$ . Si hay un $x'\in X'$ tal que existe un número infinito de $y'\in Y'$ tal que $(x',y')$ tiene color $\alpha$ Entonces hemos terminado. $x,x'$ y $y_1,y_2$ tal que $(x',y_1)$ y $(x',y_2)$ tener color $\alpha$ . En caso contrario, observe que el conjunto $C'=C\setminus\alpha$ tiene $c-1$ elementos, y para cada $x\in X'$ los únicos colores que aparecen un número infinito de veces entre los pares $(x,y)$ están en $C'$ . Por la hipótesis inductiva existen $x_1,x_2\in X'$ y $y_1,y_2\in Y'$ tal que $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ todos tienen el mismo color.

Answer 4

Primero decidiremos cómo elegir las filas. Básicamente hay tres colores, así que aplicando el principio del casillero, si elegimos que el número mínimo de filas sea 4, en el peor de los casos se repetirá un color.

Ahora, para elegir el número mínimo de columnas de 4 filas, elegiremos 2 filas cualesquiera y les asignaremos el mismo color, ya sea rojo, azul o verde. Esto nos llevará a la combinación de 18 opciones posibles (4C2*3 (para cada color)).

Por lo tanto, aplicando de nuevo la regla de la colombofilia, debería haber al menos 19 (18+1) columnas para que dos colores en 4 filas pudieran ser iguales.