Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known.
Anyone feel up to trying 5-colorings? ;)
The following question arises out of Ramsey Theory.
Consider a $k$-coloring of the $n$-by-$m$ grid graph. A
monochromatic rectangle exists whenever four cells with the same color are arranged as the corners of some rectangle. For example, $(0,0), (0,1), (1,1),$ and $(1,0)$ form a monochromatic rectangle if they have the same color. Similarly, $(2,2), (2,6), (3,6),$ and $(3,2)$ form a monochromatic rectangle, if colored with the same color.
Question: Does there exist a $4$-coloring of the $17$-by-$17$ grid graph that does not contain a monochromatic rectangle? If so, provide the explicit coloring.
Some known facts:
- $16$-by-$17$ is $4$-colorable without a monochromatic rectangle, but the known coloring scheme does not appear to extend to the $17$-by-$17$ case. (I'm omitting the known $16$-by-$17$ coloring because it would very likely be a red herring for deciding $17$-by-$17$.)
- $18$-by-$19$ is NOT $4$-colorable without a monochromatic rectangle.
- $17$-by-$18$ and $18$-by-$18$ are also unknown cases; an answer to these would be interesting as well.
Disclaimer: Bill Gasarch has a $289 (USD) bounty on a positive answer to this question; you can reach him through his blog. A note on etiquette: I'll make sure he knows the source of any correct answer (should one arise).
He brought it up again during a rump session at Barriers II, and I find it interesting, so I'm forwarding the question here (without his knowledge; though I highly doubt he would mind).