Title: A variant of the Heilbronn's triangle problem: the Motzkin-Schmidt strip problem

Speaker: Jozsef Beck, Rutgers University

Date: Tuesday, September 17, 2002

Location: DIMACS Seminar Room, CoRE Building, Room 431A, Rutgers University, Busch Campus, Piscataway, NJ.

Abstract:

The Heilbronn's triangle problem is a famous problem in combinatorial geometry. It goes as follows: Assume we have n points in the unit square. This n-set determines ``n-choose-3'' triangles. How small is the smallest triangle area? Is it o(1)/n? (o(1) tends to 0 as n tends to infinity.) This question was answered affirmatively 50 years ago by K.F. Roth, and since then we have several big improvements of the upper bound.

The following variant, however, resisted every attempt and remained unsolved: instead of finding a triangle of area o(1)/n, we want to find a strip of width o(1)/n which contains (at least) 3 points. (Of course a strip of width o(1)/n in the unit square has area o(1)/n.) This is the ``Motzkin-Schmidt strip problem". (Motzkin asked the question 40 years ago, and W.M. Schmidt, who was the first to improve on Roth's upper bound in the Heilbroon's triangle problem, rediscoverd the problem somewhat later.) We outline the proof of the following quantitative result: there is a strip of width o(1)/n with o(1)=(log n)^{-1/10} which contains at least 3 points.