Welcome to MathOverflow

Question

6

1

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

flag	asked Oct 23 2009 at 22:56 Patrick LaVictoire 63●3

	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 2009 at 15:40
	Oops, that should be [10]^2, so 90 vertices. Still seems too big, though. – Jonah Ostroff Oct 24 2009 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 2009 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 2009 at 22:39

Ricky Liu · Accepted Answer · 2009-10-24 00:22:19Z UTC

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 Z² 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.

Jonah Ostroff · Answer 2 · 2009-10-24 00:30:34Z UTC

Nope.

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

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.