6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Oct 24, 2009 at 15:40
  • $\begingroup$ Oops, that should be [10]^2, so 90 vertices. Still seems too big, though. $\endgroup$ Oct 24, 2009 at 16:10
  • $\begingroup$ 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. $\endgroup$ Oct 24, 2009 at 16:40
  • $\begingroup$ And now with 6, for anyone still interested: {(1,1), (1,2), (2,1), (2,2), (2,3), (3,1)} $\endgroup$ Oct 29, 2009 at 22:39

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Both of them nice proofs. Would split the check equally if that were an option. Thanks! $\endgroup$ Oct 24, 2009 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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