Hello all,

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.

[New users cannot link images, so here is the picture: Grid example]

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:

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.)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.?

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?