Originator: Bill Gasarch (presented by Beth Kupin - REGS 2011)
Definitions: A rectangle set in an m-by-n grid of squares is any set of four squares that form the corners of an axis-parallel rectangle. An m-by-n grid is k-colorable if each square can be given one of k colors so that no rectangle set is monochromatic.
Background: This is a restatement of the much older question of coloring the edges of a complete bipartite graph to avoid a monochromatic 4-cycle. However, we are primarily interested in not asymptotics but rather exact results for grids of fixed size.
Question 1: Is the 17-by-17 grid 4-colorable?
Comments: This question has been studied by Bill Gasarch and others, and a fair amount is known (see [FGGP]). In particular, the 2-colorable and 3-colorable grids have been completely characterized. The 17-by-17 grid is one of the few remaining grids for which 4-colorability has not been determined.
It is known that the 16-by-16 grid is 4-colorable, as is the set obtained by deleting any one square from the 17-by-17 grid ([P]). The largest color class in such a coloring must have size 73 or 74 (there is none larger), and in fact there is only one such set of size 74, up to isomorphism. For a more complete explanation, see [B] or [K].
Question 2: What is known about k-colorability for higher k from the perspective of graph Ramsey Theory? Can the bounds be improved for small grid sizes?
Question 3: What happens if the rectangular grid is replaced with the triangular grid, and the forbidden monochromatic sets are now any three triangles that form the corners of an arbitrarily large, axis-aligned equilateral triangle?
Comment: Here one is seeking a "homothetic copy" of an monochromatic equilateral triangle in a triangular grid (translation and scaling are allowed). Gallai's Theorem about the existence of homothetes of a fixed set of points implies that for any fixed k, a sufficiently large triangular grid cannot be k-colored (see [GRS]). The proof of Gallai's Theorem uses van der Waerden's Theorem. Indeed, van der Warden's Theorem can be used in a fairly easy argument by induction on the number of colors to prove the statement directly.
Question 4: What about other classes of forbidden sets for the triangular grid? What types of forbidden sets would be interesting on the hexagonal grid?
References:
[FGGP] S. Fenner, W. Gasarch, C. Glover, S. Purewal. Rectangle Free Coloring of
Grids. PDF
[B] Bill Gasarch,
blog post on the topic.
[GRS] R.L. Graham, B.L. Rothschild, and J.H. Spencer,
Ramsey Theory (Wiley-Interscience, 1980), Section 2.3.
[K] E. Kupin. Notes on 4-coloring the 17 by 17 Grid: PDF
[P]
R. Puttagunta,
4-coloring
of the 17-by-17 grid except for 1 square.