The question of chromatic number of the plane is really akin to the measure counterexamples, it's talking about counting things that are actually uncountable. It's really a question about algebraic number fields---the chromatic number of the plane is the sup over all finite extensions of Q of the chromatic number for that algebraic number field. (for any graph containing 0 and 1 whose vertices are not algebraic, they're in a transcendental extension which means you can substitute complex variables for a transcendence basis --- and vary them to be algebraic). There's some kind of weird transfinite induction `construction' of a tiling of the plane with c colors from tilings of all algebraic number fields with c colors, but it's highly non-constructive. What's known about the chromatic number of the plane? I'm curious whether enough is known to be able to prove there can't be a measurable best coloring. Bill On Apr 19, 2005, at 6:33 AM, David Wilson wrote:
When I am mulling over a problem and I wish to consult math-fun about it, I tend to dumb-down the question I ask to math-fun, in order to avoid voluminous background material. In this case, my ruminations were on the chromatic number of the plane.
To start with, here is a little theorem:
Theorem: If c is the chromatic number of the plane, each of the c colors applies to an uncountable number of points in the plane.
Proof: Let c be the chromatic number of the plane, and let the plane be c-colored so that no two points at unit distance have the same color. Suppose only a countable set of points S(A) have color A. Choose finite c-color Moser graph M in the plane (Erdos et al proved it exists). Let V be the finite set of vectors between pairs of vertices of M, including the zero vector.
Let S'(A) = {a+v: a in S(A), v in V}. Then, any translation of M having a vertex in S(A) has all vertices in S'(A). Since S'(A) is countable, some point P of the plane is not in S'(A). Translate M to M' with vertex P. P is not in S'(A), so no vertex of M' is in S(A), and M' has no vertex of color A. This means that M' is (c-1)-colored, but it is not (c-1)-colorable, so two adjacent vertices must have the same color, corresponding to two points of the plane at unit distance with the same color. This contradicts our coloring of the plane, and so S(A) must be uncountable, QED.
In tesselation-style colorings of the plane, such as the 7-coloring used to show c <= 7, the uncountability of points in each color is evident. However, since no tesselation-style coloring has yet been found for c <= 6, I was drawn to consider other types of colorings. Specifically, I wondered if there might not be a c-coloring in which every region of the plane included points of all colors.
It was at that point I went out of my depth. My gut feeling was that if such a c-coloring existed, the points of color c would be of positive measure in each region of the plane. But I didn't even know of two sets of positive measure on every interval of the reals, hence my question.
I suppose my hope was to find some miraculous decision function that would allow me to decide which points in the plane were of what color, with each color being somewise equally and uniformly distributed over the plane and every pair of points at distance 1 of different colors. The hope seems pretty naive.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun