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

I ran into this obstacle in a harmonic analysis problem; I know epsilon about coloring problems.

Is it possible to finitely color Z^2 so that the points (x,a) and (a,y) are differently colored for every x, y and a in the integers (excepting, of course, the trivial cases x=y=a)?

share|cite|improve this question
I don't know if there's a better place to put this, but here's a follow-up question: what do the smallest subgraphs that require k colors look like? Before I worked out the solution below, I had trouble finding anything that that wasn't three-colorable. As per my proof, [11]<sup>2</sup> minus the diagonal should require four colors, but 110 vertices seems like overkill. Is there a smaller example for k=4? – Jonah Ostroff Oct 24 '09 at 15:40
Oops, that should be [10]^2, so 90 vertices. Still seems too big, though. – Jonah Ostroff Oct 24 '09 at 16:10
Oh, here we go. 7 vertices: {(1,1), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)}. This is the four-chromatic graph generally used to show that the unit-distance plane graph isn't three-colorable (in the sense of the Hadwiger-Nelson problem), plus a few edges. I suspect it's minimal, though I could be wrong. – Jonah Ostroff Oct 24 '09 at 16:40
And now with 6, for anyone still interested: {(1,1), (1,2), (2,1), (2,2), (2,3), (3,1)} – Jonah Ostroff Oct 29 '09 at 22:39
up vote 11 down vote accepted

No, this isn't possible. First note that the question is the same if we replace Z with any infinite subset of Z. Now, suppose it were possible to color Z2 with k colors, where k is minimum. Pick any row r. We can find an infinite set S of integers not containing r such that for x in S, all the (x, r) have the same color c. No point in SxS can have color c, so SxS is colored with k-1 colors. But this contradicts the minimality of k.

share|cite|improve this answer


Suppose this were possible. For z \in Z, let Rz be the colors that appear in the row {(x,z) : x≠z \in Z}, and let Cz be the colors that appear in the column {(z,y) : y≠z \in Z}. The coloring condition is that each Cz and Rz is disjoint. Since there are finitely many possibilities for each set, find distinct z and z' where Rz = Rz', and Cz = Cz'. What color is (z,z')? Well, it's in Rz' (and not Cz'), and it's in Cz (but not Rz). So it's both in Rz and not: a contradiction.

(Ninja'd. Drat. Well, different proof at least.)

share|cite|improve this answer
Both of them nice proofs. Would split the check equally if that were an option. Thanks! – Patrick LaVictoire Oct 24 '09 at 1:48

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.