Sunday, March 23, 2008

Coloring lattices

A problem:

You have an infinite (2-dimensional) chessboard. Can you 2-color the squares of the chessboard so that a chess king, starting on any one square, can move to at most n distinct squares of the same color for some fixed n? (I.e., that all the connected monochromatic regions are of bounded size?)

If you think about it for a few minutes, it should become obvious that the answer is no. Proving it is a bit more difficult. I don't wanna cut this post (also I'm not sure how to in Blogger), so I'll just put the proof outline in rot13 below.

Fhccbfr bgurejvfr. Vg'f pyrne gung n zbabpuebzngvp ertvba arrqf gb or pbzcyrgryl fheebhaqrq ol n ertvba bs gur bccbfvgr pbybe; vg'f nyfb boivbhf gung gur nern bs gur bhgre ertvba cyhf gur rairybcrq fdhnerf vf fgevpgyl terngre guna gur nern bs gur rairybcrq fdhnerf. Abj, vg'f rnfl gb fubj gung nf gur nern bs n pbaarpgrq ertvba nccebnpurf vasvavgl, fb qbrf gur nern bs na rairybcvat ertvba. Chggvat gurfr snpgf gbtrgure, gur gurberz rnfvyl sbyybjf.

Not that bad, but what happens if we increase the number of colors (and the number of dimensions)? Using an inductive argument, it's possible to color Z^d with (d+1) colors and get regions of bounded size; but I don't see any easy combinatorial argument that gives any (non-constant) lower bound. Any ideas?