It is fairly well known that for any $k$-coloring of $\mathbb{Z}^2$, it is impossible to color the vertices such that you never get a rectangle with axes parallel to the x and y-axis with vertices of the same color. In fact, it is known that you cannot color an $(k+1) \times (\frac{k^2(k+1)}{2}+1)$ lattice of points that meets this criterion. For example, you cannot 2-color the $3\times 7$ lattice in this manner. You can, however, color the $(k+1) \times (\frac{k^2(k+1)}{2})$ lattice in this way. One such successful 2-coloring of the $3\times 6$ lattice is below.
So, if the $3\times 6$ lattice is 2-colorable in this fashion, it is a natural question to ask, "what about the $6\times 6$ lattice?". As it turns out, the answer to this is "no". We can prove this by first showing you cannot 2-color the $5\times 6$ lattice.
After some experimentation, one sees that the only successful 2-coloring of the $4\times 6$ lattice is some permutation of the rows and columns of the below.
If one adds a column to the right, it becomes apparent that the top-right vertex can neither be red nor blue: in the case of the former, we eventually see that the fourth-row vertex cannot be red or blue, and in the case of the latter, we see the same for the third-row vertex. Therefore, the $6\times 6$ lattice cannot be colored like this – QED.
However, what about the $5\times 5$ lattice? It becomes clear that we essentially have six unique ways to color in the first three rows, seen below (again, barring permutations of the rows and columns). I know that out of these six, you cannot 2-color the top-left one successfully. I have yet to try the others, but would not be surprised to find you cannot achieve this for any configuration.
For what it is worth, it can be shown that yes, the $4\times 4$ lattice can be successfully colored like this, which will be shown at the end. However, this is only for 2-coloring. What about 3-coloring, or 4-coloring? What about $n$-coloring in general? If I had to make a conjecture, the most I would be willing to say is that you can never make a $(\frac{k^2(k+1)}{2})\times (\frac{k^2(k+1)}{2})$ lattice that can be colored like this, but even for that I don't know where to start proving it, and I don't know how to move that upper bound any lower. Any thoughts?
Best Answer
Here's a generalization of the $(k+1) \times (\frac{k^2(k+1)}{2}+1)$ proof to square grids.
Suppose we have an $n \times n$ grid. If a column of the grid has $n_i$ squares of the $i^{\text{th}}$ color, with $n_1 + \dots + n_k = n$, then it has $\binom{n_1}{2} + \dots + \binom{n_k}{2}$ monochromatic pairs of squares, which can never repeat in the same color in a different column. By convexity, this number is at least $k\binom{n/k}{2}$.
The total supply of such pairs is $k \binom n2$: there are $\binom n2$ pairs of squares, and each pair can be monochromatic in $k$ different colors. So the constraint on $n$ is that $nk \binom{n/k}{2} \le k \binom n2$: we can pick $n$ columns without exhausting the supply. This inequality just barely fails for $n = k^2+k$: we get $\frac12 k^2(k+1)(k^2+k)$ on the left and $\frac12 k^2(k+1)(k^2+k-1)$ on the right.
Therefore a $(k^2+k) \times (k^2+k)$ lattice can never be colored, but there is still hope for a $(k^2+k-1) \times (k^2+k-1)$ lattice.
We can destroy this hope and reduce the bound by $1$, incidentally proving that when $k=2$, $4\times 4$ is best possible.
In this $(k^2+k-1) \times (k^2+k-1)$ lattice, the most even way to color a column is to use one color $k$ times and the others $k+1$ times, which uses up $\binom k2 + (k-1)\binom{k+1}{2} = \frac12 k(k^2+k-2)$ monochromatic pairs. We have a total supply of $k \binom{k^2+k-1}{2}$ monochromatic pairs; dividing by $k^2+k-1$, that gives us $\frac 12k(k^2+k-2)$ per column. So the only way we have any chance is to color each column in the most even way possible.
In every column, one color is underused. With $k^2+k-1$ columns, not every color can be underused $k+1$ times; one color is only underused $k$ times. Across all $k^2+k-1$ columns, that color appears in $k\binom k2 + (k^2-1)\binom{k+1}{2} = $ monochromatic pairs, which is more than the $\binom{k^2+k-1}{2}$ monochromatic pairs of that color we are allowed. Some monochromatic pair repeats in that column, giving us a rectangle.
Now we have an upper bound of $(k^2+k-2) \times (k^2+k-2)$, which is possible for $k=2$.
I don't know if this upper bound is tight, but it is the right order of magnitude: at least for all prime powers $k$, we can $k$-color the $k^2 \times (k^2+k)$ lattice. Here is an example when $k=3$:
The idea is to find $k+1$ partitions of ${1,\dots,k^2}$ so that no two elements are in the same partition together. To use a partition to color a column, assign color to each part of the partition, and use that color on every element of that part. Each partition can be used on $k$ columns if we permute the colors assigned to the parts. in the grid above, the first $3$ columns use the partition $\{1,2,3\} \cup \{4,5,6\} \cup \{7,8,9\}$. The next $3$ use the partition $\{1,5,9\} \cup \{2,6,7\} \cup \{3,4,8\}$.
How do we find these $k+1$ partitions? We identify $\{1,\dots,k^2\}$ with $\mathbb F_k^2$, where $\mathbb F_k$ is the field with $k$ elements. The plane $\mathbb F_k^2$ can be partitioned into the set of all lines with a given slope. The slope of a line can be an element of $\mathbb F_k$, or $\infty$ for vertical lines: $k+1$ possibilities. Any two points are in only one line, so they are together in only one partition.
In particular, the $k^2 \times k^2$ square lattice can also be $k$-colored when $k$ is a prime power. So the optimal value is somewhere between $k^2$ and $k^2+k-2$.