From:           gfroyle@water.waterloo.edu (G.F.Royle)
Newsgroups:     sci.math
Subject:        Re: Putnam - chromatic number of the plane
Keywords:       Putnam,putnam,competition,math
Date:           9 Dec 88 05:59:11 GMT
Organization:   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.math
Subject:        References for Putnam problem A-4 (chromatic number)
Date:           12 Jan 89 00:46:24 GMT
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 EST
From:           Ricky Pollack <pollack@geometry.cims.nyu.edu>
To:             geometry@cims.nyu.edu
Subject:        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}
`