From:gfroyle@water.waterloo.edu (G.F.Royle)Newsgroups:sci.mathSubject:Re: Putnam - chromatic number of the planeKeywords:Putnam,putnam,competition,mathDate:9 Dec 88 05:59:11 GMTOrganization:U of Waterloo, Ontario

In article <10370@umn-cs.CS.UMN.EDU>, raghavan@umn-cs.CS.UMN.EDU (Vijay Raghavan) writes: > > This problem has probably been studied. Can anybody exhibit a colouring > which demonstrates that 4 colours suffice to have no two points on the > plane at a distance of 1 inch? Or prove that 4 colours do not suffice? > Anybody know of any references? > > Vijay Raghavan > This is indeed a long standing problem. Usually stated as follows: Let G be the graph with vertices the points of the plane and two points joined if they are at distance one from each other. Then the question is: What is the chromatic number of this graph?? (the smallest number of colours with which the vertices can be coloured so that adjacent vertices have different colours). This is one of Paul Erdos' pet problems and I have heard him speak on it a couple of times. The known results (from memory and now at least a couple of years old) are (1) The graph can be 7-coloured (try a hexagonal tessellation) (2) There is a configuration that requires 4 colours (the one demanded by the Putnam problem will do) Thus, if chi is the chromatic number then 4<chi<7. Other than that the true number could be anywhere... A typical combinatorial puzzler - easy to state, impossible to prove. A further result due to Erdos is that if this graph requires k colours, then some FINITE subgraph of it also requires k colours. However there is no immediate reason to believe that if there IS a configuration that requires 5 colours then it is on less than <billions> of vertices (substitute your own large number). Similar problems have also been studied for the integer line (where you join two integers if they differ by an amount in some fixed set - say {1,2,5} or whatever). This is all from memory and I have no references, so anyone with more up-to-date info please feel free to correct me... Gordon

From:ilan@Gang-of-Four.Stanford.EDU (Ilan Vardi)Newsgroups:sci.mathSubject:References for Putnam problem A-4 (chromatic number)Date:12 Jan 89 00:46:24 GMTReply-To:ilan@Gang-of-Four.Stanford.EDU (Ilan Vardi)Organization:Computer Science Department, Stanford University

Here is a pretty good list of references for the chromatic number of the plane (i.e., how many colors do you need so that no two points 1 away are the same color) up to around 1982 (though the publication dates are up to 1985). This asks for the chromatic number of the graph where two points in R^2 are connected if they are distance 1 apart. Let this chromatic number be chi(2) and in general let chi(n) be the chromatic number of R^n. By a theorem in [2] this is equivalent to finding what the maximum chromatic number of a finite subgraph of this infinite graph is. [1] H. Hadwiger, ``Ein Ueberdeckungssatz f\"ur den Euklidischen Raum,'' Portugal. Math. #4 (1944), p.140-144 This seems to be the original reference for the problem [2] N.G. de Bruijn and P. Erd\"os, ``A Color Problem for Infinite Graphs and a Problem in the Theory of Relations,'' Nederl. Akad. Wetensch. (Indag Math) #13 (1951), p. 371-373. [3] H. Hadwiger, ``Ungel\"oste Probleme No. 40,'' Elemente der Math. #16 (1961), p. 103-104. Gives the upper bound of 7 with the hexagonal tiling and also a reference to a Portugese journal where it appeared. [4] L. Moser and W. Moser, ``Solution to Problem 10,'' Canad. Math. Bull. #4 (1961), p. 187-189. Shows that any 6 points in the plane only need 3 colors but gives 7 points that require 4 (``the Moser Graph'' see [7]). [5] Paul Erd\"os, Frank Harary, and William T. Tutte, ``On the Dimension of a Graph,'' Mathematika #12 (1965), p. 118-122. States that 3<chi(2)<8. Proves that chi(n) is finite for all n. [6] P. Erd\"os, ``Problems and Results in Combinatorial Geometry,'' in ``Discrete Geometry and Convexity,'' Edited by Jacob E. Goodman, Erwin Lutwak, Joseph Malkevitch, and Richard Pollack, Annals of the New York Academy of Sciences Vol. 440, New York Academy of Sciences 1985, Pages 1-11. States that 3<chi(n)<8 and ``I am almost sure that chi(2)>4.'' States a question of L. Moser: Let R be large and S a measurable set in the circle of radius R so that no two points of S have distance 1. Denote by m(S) the measure of S. Determine Lim_{R => infty} max m(S)/R^2. Erd\"os conjectures that this limit is less than 1/4. Erd\"os asks the following: ``Let S be a subset of the plane. Join two points of S if their distances is 1. This gives a graph G(S). Assume that the girth (shortest circuit) of G(S) is k. Can its chromatic number be greater than 3? Wormald proved that such a graph exists for k<6. The problem is open for k>5. Wormald suggested that this method may work for k=6, but probably a new idea is needed for k>6. A related (perhaps identical) question is: `Does G(S) have a subgraph that has girth k and chromatic number 4?' '' [7] N. Wormald, ``A 4-chromatic graph with a special plane drawing,'' J. Austr. Math. Soc. Ser. A #28 (1970), p. 1-8. The reference for the above question. [8] R.L. Graham, ``Old and New Euclidean Ramsey Theorems,'' in ``Discrete Geometry and Convexity,'' Edited by Jacob E. Goodman, Erwin Lutwak, Joseph Malkevitch, and Richard Pollack, Annals of the New York Academy of Sciences Vol. 440, New York Academy of Sciences 1985, Pages 20-30. States that the best current bounds are 3<chi(2)<8. Calls the graph in [3] the Moser graph. Quotes the result of Frankl and Wilson [8] that chi(n) grows exponentially in n settling an earlier conjecture of Erd\"os (I don't know the reference for this). The best available bounds for this are (1+ o(1)) (1.2)^n \le chi(n) \le (3+ o(1))^n. [9] P. Frankl and R.M. Wilson, ``Intersection Theorems with Geometric Consequences,'' Combinatorica #1 (1981), p. 357-368. [10] H. Hadwiger, H. Debrunner, and V.L. Klee, ``Combinatorial Geometry in the Plane,'' Holt, Rinehart & Winston, New York (English edition, 1964). [11] D.R. Woodall, ``Distances Realized by Sets Covering the Plane,'' Journal of Combinatorial Theory (A) #14 (1973), p. 187-200. Among other things, shows that rational points in the plane can be two colored. [12] L. A. Sz\'ekely, ``Measurable Chromatic Number of Geometric Graphs and Sets without some Distances in Euclidean Space,'' Combinatorica #4 (1984), p.213-218. Considers \chi_m(R^2), the measurable chromatic number, where sets of one color must be Lebesgue measurable. He conjectures that \chi_m(R^2) is not equal to \chi(R^2) (if the Axiom of Choice is false). [13] Martin Gardner, ``Scientific American,'' October 1960, p. 160. [14] Martin Gardner, ``Wheels, Life and other Mathematical Amusements,'' W.H. Freeman and Co., New York 1983, pages 195-196. This occurs in a chapter on mathematical problems including the 3x+1 problem. I think that his references are wrong, including attributing the problem to Erd\"os and claiming that Charles Trigg had original solutions in ``Problem 133,'' Crux Mathematicorum, Vol. 2, 1976, pages 144-150.

Date:Mon, 27 Nov 95 10:33:29 ESTFrom:Ricky Pollack <pollack@geometry.cims.nyu.edu>To:geometry@cims.nyu.eduSubject:geometry seminar

\documentstyle[12pt]{article} \pagestyle{empty} \newcommand{\R}{{\bf R}} \begin{document} \title{Geometry Seminar\\ Tuesday November 28in room 613 WWH at 6:00 P.M\\ \bigskip \bigskip {\bf Euclidean Ramsey Theorems }} \date{} \author{ G\'eza T\'oth\\Courant Institute } \maketitle \pagestyle{empty} \thispagestyle{empty} \begin{abstract} \begin{sloppypar} Euclidean Ramsey Theory started with the famous Hadwiger-Nelson problem: how many colors are needed to color the points of the plane if no two points at unit distance receive the same color. After surveying some of the most important results in this field, we prove some new theorems in low dimensions. For instance, for any rectangle $T$ and for any $2$-coloring of the points of the $5$-dimensional Euclidean space, one can always find a rectangle $T'$ congruent to $T$, all of whose vertices are of the same color. This improves a result of Erd\H{o}s-Graham-Montgomery-Rothschild-Spencer-Straus. \end{sloppypar} \end{abstract} \end{document}