School of Physical Sciences
          ALGEBRA AND COMBINATORICS SEMINAR

       		   Fri Feb 29 2008 2pm

   "Elementary" open problems in discrete geometry

                  Moshe Rosenfeld

         University of Washington Tacoma, USA


Abstract
Which problems attain great notoriety and which are delegated to collect
dust on a shelf?

Usually, elementary problems tend to attract attention because they are
very easy to understand and look "solvable".  It is a mystery to me why
some attract a lot of attention while others lie hibernating waiting for
some new fresh ideas.

In their recent interesting book Research Problems in Discrete Geometry
(Springer, New York 2005) P. Brass, W. Moser, J. Pach wrote:

"Although Discrete Geometry has a rich history extending more than 150
years, it abounds in open problems that even a high-school student can
understand and appreciate. Some of these problems are notoriously
difficult and are intimately related to deep questions in other fields of
mathematics. But many problems, even old ones, can be solved by a clever
undergraduate or a high-school student equipped with an ingenious idea and
the kinds of skills used in a mathematical olympiad."

In this talk I'll survey some "elementary" open problems in discrete
geometry. Some of these problems are characterized by constructions
yielding lower bounds and upper bounds. For instance, Nelson's problem,
coloring the points of R^2 so that points at unit distance have distinct
colors is a typical, probably the most popular among these problems. While
for this problem, also known as the unit-distance graph problem, the
bounds 4 \leq \chi(R^2) \leq 7 where known over 58 years ago, so far no
one was able to improve them. This led to many variations and hundreds of
related problems and papers.

In this talk I'll survey some similar problems in combinatorial geometry.
Among them:

1.      The Unit Distance Graph.
2.      The odd-distance graph.
3.      Partitioning a square into rectangles.
4.      Hadwiger-deBrunner (p,q) problem.


All welcome.