[math-fun] coloring unit-distance graph in the plane
As previous posters pointed out, if you want to color the plane so that any 2 points at distance=1 have different colors than you need at least 4 colors (proof:Moser or Golomb's graphs) while 7 colors are known to suffice (proof: tiling by regular hexagons, each monocolored). http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane I now point out, that if your coloring is required to be PERIODIC and I get to choose the period-parallelogram, then one can prove 7 colors are both necessary and sufficient. Reason is, the tiling of the plane by equilateral triangles, is, in fact, viewed modulo an appropriate period parallelogram, the complete graph K7. Here is a picture drawn by Steven Taschuk: http://amotlpaa.nfshost.com/math/k7torus.html This incidentally also shows that torus graphs can require 7 colors (which also is known to suffice). Meanwhile a hex-tiling construction proves sufficiency. The catch is, that the period-parallelogram for the "necessary" is not the same as for the "sufficient"!
Here's an interesting possible attack on this problem. Let N be an integer with a ton of representations of the form a^2+b^2-ab (equivalent form: u^2+3*v^2). For example N=7*13*19*31*37 works well, (product of K primes that are each 1 mod 3 will have a number T of reps exponential in K). Now within the set of vertices of the equilateral triangle lattice of sidelength=1, consider the distance=sqrt(N) graph. This graph is countably infinite and regular with (arbitrarily large) valency T. Now ask your computer: what is the chromatic number of some finite subgraph of it? That will be a lower bound on the chromatic number of the plane distance=1 graph. The analogous attack can be done using any underlying 2-variable integer quadratic form (not necessarily a^2+b^2-ab), and which quadratic form and which N would yield the best results, I do not know. Because of the large valency it seems plausible you might get a large chromatic number. Unfortunately the specific N just suggested would yield a rather large graph... your poor computer would be laboring trying to find its chromatic number...
Hi Warren, I was thinking along similar lines. Consider the triangular lattice, and consider all the distances you can get between pairs of lattice points, but not between two points in the same sublattice (corresponding to the same color in a 3-coloring of the lattice). These distances separate pairs of points that we can force to be different colors. Now, suppose there are two distances in this set with ratio phi (the golden ratio). I think actually there are no such pairs, which is a nice problem in algebra... but if there were, then you could build a K_5, which would give a lower bound of 5 on the chromatic number of the plane. Cris On Apr 3, 2013, at 6:51 PM, Warren D Smith wrote:
Here's an interesting possible attack on this problem. Let N be an integer with a ton of representations of the form a^2+b^2-ab (equivalent form: u^2+3*v^2). For example N=7*13*19*31*37 works well, (product of K primes that are each 1 mod 3 will have a number T of reps exponential in K).
Now within the set of vertices of the equilateral triangle lattice of sidelength=1, consider the distance=sqrt(N) graph. This graph is countably infinite and regular with (arbitrarily large) valency T. Now ask your computer: what is the chromatic number of some finite subgraph of it? That will be a lower bound on the chromatic number of the plane distance=1 graph.
The analogous attack can be done using any underlying 2-variable integer quadratic form (not necessarily a^2+b^2-ab), and which quadratic form and which N would yield the best results, I do not know. Because of the large valency it seems plausible you might get a large chromatic number. Unfortunately the specific N just suggested would yield a rather large graph... your poor computer would be laboring trying to find its chromatic number...
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
nice. we can draw a K_7 on the torus. In fact, I remember a Martin Gardner column with a (non-convex) polyhedron, with the topology of a torus, where each side shared an edge with the other 6! Cris On Apr 3, 2013, at 6:21 PM, Warren D Smith wrote:
As previous posters pointed out, if you want to color the plane so that any 2 points at distance=1 have different colors than you need at least 4 colors (proof:Moser or Golomb's graphs) while 7 colors are known to suffice (proof: tiling by regular hexagons, each monocolored). http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane
I now point out, that if your coloring is required to be PERIODIC and I get to choose the period-parallelogram, then one can prove 7 colors are both necessary and sufficient. Reason is, the tiling of the plane by equilateral triangles, is, in fact, viewed modulo an appropriate period parallelogram, the complete graph K7. Here is a picture drawn by Steven Taschuk: http://amotlpaa.nfshost.com/math/k7torus.html This incidentally also shows that torus graphs can require 7 colors (which also is known to suffice). Meanwhile a hex-tiling construction proves sufficiency.
The catch is, that the period-parallelogram for the "necessary" is not the same as for the "sufficient"!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
On this subject, there's a lovely symmetrical picture of this: Create a rosette of 7 congruent regular hexagons: * a * f b * e * * c * d * * i * * * * * i * * h * * * * * * h * * g * * * * * g * * f * a * * e * b d * c * Now identify the 18 exposed edges, by translations, in pairs. The result is a highly symmetrical torus, that is clearly tiled by 7 congruent smaller tori, each of which touches the other 6, showing that ch(T^2) >= 7. Hmm: QUESTION: What is the chromatic number of the unit distance graph of this torus? (Assuming that the distance between the centers of any two hexagons is exactly 1.) --Dan On 2013-04-03, at 6:44 PM, Cris Moore wrote:
we can draw a K_7 on the torus. In fact, I remember a Martin Gardner column with a (non-convex) polyhedron, with the topology of a torus, where each side shared an edge with the other 6!
That would be the Szilassi polyhedron. I've always wondered if there is any cool connection to the Fano Plane.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun- bounces@mailman.xmission.com] On Behalf Of Cris Moore Sent: Wednesday, April 03, 2013 9:45 PM To: math-fun Subject: Re: [math-fun] coloring unit-distance graph in the plane
nice. we can draw a K_7 on the torus. In fact, I remember a Martin Gardner column with a (non-convex) polyhedron, with the topology of a torus, where each side shared an edge with the other 6!
Cris
participants (4)
-
Cris Moore -
Dan Asimov -
David Wilson -
Warren D Smith