Permutations of Grid Colorings

Question

This question arises out of a Ramsey-theoretic study related (but tangential) to this question on CSTheory: Grid $k$-coloring without monochromatic rectangles.

Background:

In general, we consider the $n$-by-$m$ grid graph, $G_{n, m}$ (that is, a chessboard-like graph), are given a number of allowed colors $c$, and our goal is to assign one of the allowed colors to each vertex of $G_{n, m}$ such that no set of four vertices arranged in an axis-parallel rectangle is colored monochromatically. For example, the following picture (in link) illustrates a legal 2-coloring of $G_{4, 4}$ (on the left) and an illegal 2-coloring of $G_{4, 4}$ (on the right). The monochromatic rectangle induced by the color assignment is marked by $\times$'s.

Further, it is known that any permutation of the rows and/or columns of grid graphs preserves the legality of a given coloring. For example, we can exchange every vertex in the 2nd column of the above, left grid with every vertex in the 3rd column of the above, left grid, and the resulting coloring will be a legal coloring of $G_{4, 4}$, and so forth. (Similarly, exchanging all of one color's assignments with all of another color's assignments preserves legality of colorings, but this is somewhat less interesting; e.g., we can exchange every red color with every blue color, and the coloring is still legal.)

Question:

Now suppose you are given a $c$-coloring of $G_{n, m}$, for arbitrary integers $n, m, c \ge 2$, and a promise that this coloring is legal. Further, let there be some rectangle chosen -- adversarially -- that is hidden from you until the end of the problem. Within this rectangle, the adversary also chooses two of the four cells and hides this choice from you. (Clarification: The four cells of the rectangle chosen are always colored 3 with one color, and 1 with another, and two of the cells colored identically are selected; otherwise a solution, as described below, is not immediately guaranteed.)

The new goal is to provide a new, legal $c$-coloring of $G_{n, m}$ (or even a set of new, legal $c$-colorings of $G_{n, m}$) such that (in at least one of the colorings) the two hidden cells chosen by the adversary are colored differently. And in particular, you want to minimize the size of the set of new colorings you must provide in order to be guaranteed to "win."

Note that if you knew which rectangle (or which two cells) were chosen, that this problem is trivial -- the given coloring contains no monochromatic rectangles, so you just permute the appropriate rows or columns so that the two cells in question are colored differently. In particular, this observation guarantees that the problem always has a solution; the trick is to find it.

For clarity, as this problem comes from computational complexity: You may assume you have unbounded computational power; this is not about resource-bounded computation, rather it's about mathematical existence.

Here are the underlying questions:

1. Can you always win by providing a set of colorings of constant size, $O(1)$? That is, independent of the size of the grid graph? (We can assume that $c$ is a constant for this purpose.)

2. Or similarly, are you forced to always provide a set of colorings that depends on $n$ or $m$, e.g. $\Omega(n)$ (resp. $\Omega(m)$), etc.?

3. Further, supposing (2) is the case, can you always win by providing a set of colorings of $O(1)$ size if you are supplied with additional information? For (wild) example, if you are given the index of a row and a guarantee that two of the four cells of the rectangle fall in that row, can you do better?

Answer 1

O(1) is impossible even if you drop the condition of no monochromatic rectangles, and even if you know that the two cells are always chosen within a given row.

Suppose the length of the rows, $m$, is very large, say $c^k$. Fix a row. You need at least k colourings to ensure that any two cells in the row have some colouring with respect to which they differ.