# Can I finitely color Z^2 such that (x,a) and (a,y) are different for every x,y,a?

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)?

-
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

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.

-

Nope.

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.)

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