Re: [math-fun] coloring unit-distance graph in the plane
From: Cris Moore <moore@santafe.edu> 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.
--well, in spirit you may have a good idea (I do not know and feel confused)... but your idea in detail is a bust: Every distance between two points of the eq.tri. lattice is sqrt(integer) and obviously the ratio of two such, cannot be phi, since it must be sqrt(rational) and phi^2=phi+1=irrational.
aha! more generally, is it impossible to build a K_5 whose edge lengths are sqrt(integer)s? Cris On Apr 3, 2013, at 11:06 PM, Warren D Smith wrote:
Every distance between two points of the eq.tri. lattice is sqrt(integer) and obviously the ratio of two such, cannot be phi, since it must be sqrt(rational) and phi^2=phi+1=irrational.
Cristopher Moore Professor, Santa Fe Institute
It's easy to get infinitely many points in the plane with all pairwise distances integers. First of all, if you don't mind them being collinear, just take (n,0). Second, Ptolemy's Theorem implies that if two Pythagorean triangles share a hypotenuse, then their right-angled vertices are a rational distance from one another. This is a recipe for infinitely many points at pairwise rational distances (or any finite number at integer pairwise distances, after scaling), all on a circle. It you want general position, I believe the best known is seven points -- the first such integer heptagon was discovered in 2006 by Tobias Kreisel and Sascha Kurz. Ed Pegg's interactive picture of it is here: http://demonstrations.wolfram.com/LabelingTheIntegerHeptagon/ These are lovely results, but I don't think they have any bearing on the chromatic number of the plane :-/. --Michael On Thu, Apr 4, 2013 at 1:40 PM, Cris Moore <moore@santafe.edu> wrote:
aha! more generally, is it impossible to build a K_5 whose edge lengths are sqrt(integer)s?
Cris
On Apr 3, 2013, at 11:06 PM, Warren D Smith wrote:
Every distance between two points of the eq.tri. lattice is sqrt(integer) and obviously the ratio of two such, cannot be phi, since it must be sqrt(rational) and phi^2=phi+1=irrational.
Cristopher Moore Professor, Santa Fe Institute
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
According to < http://en.wikipedia.org/wiki/Erdős–Anning_theorem >, infinitely many points in the plane having only integer distances must be collinear. So I guess the hypotenuse method must always result in only finitely many points and/or collinear points. The same Wikipedia article mentions what may be equivalent to Michael's hypotenuse idea: Consider all the points on the unit circle at the angle theta such that tan(theta/4) is rational. Then these must have a rational (straight-line) distance between any two of them. Hence, any finite set of them can be uniformly scaled to have integer distances. But this can't be done for any infinite set of them. --Dan On 2013-04-04, at 11:44 AM, Michael Kleber wrote:
It's easy to get infinitely many points in the plane with all pairwise distances integers. First of all, if you don't mind them being collinear, just take (n,0). Second, Ptolemy's Theorem implies that if two Pythagorean triangles share a hypotenuse, then their right-angled vertices are a rational distance from one another. This is a recipe for infinitely many points at pairwise rational distances (or any finite number at integer pairwise distances, after scaling), all on a circle.
participants (4)
-
Cris Moore -
Dan Asimov -
Michael Kleber -
Warren D Smith