MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In this question I try to colour infinite grid paper.

There are $k$ colours and $N$ patterns (pattern is a $2\times 2$ square that coloured some way). The colouring $C$ is called the "correct" if every $2\times 2$ square in it is a pattern.
Suppose that there is correct coloring on the infinite grid plane. It seems that in this case there is a periodic correct colouring (i.e. there are $u,v$ such that for any $x,y$ cells $(x,y), (x+u,y), (x, y+v) $ are coloured same way), but I failed to prove that.

Is it true?

share|cite|improve this question
up vote 5 down vote accepted

No. Your correctness condition can be used to model sets of Wang tiles, and there are sets of Wang tiles that tile the plane only aperiodically.

share|cite|improve this answer
Do you mean "aperiodically"? thanks! – Nikita Kalinin Dec 2 '10 at 21:46
Oops, thanks for catching that typo. Fixed. – David Eppstein Dec 2 '10 at 22:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.