Department of Mathematics Colloquium
|This talk was prompted by recent results of
Koshelev of the Steklov Institute related to a 1991 conjecture of
Bialostocki, Dierker and Voxman. A 1935 Theorem of Erdös and
Szekeres states that for every integer n≥3, there exists an integer f(n), such that every set of f(n) points in the plane in general
position contains a subset of n
points which forms a convex n-gon.
This classic theorem became known as the “Happy End Theorem”. Later on,
Erdös asked whether we can
assure the existence of an empty convex n-gon, provided the set of points
is sufficiently large. Over the years Erdös' question was affirmed
for n≤5. In 1983 Horton
proved that the answer is negative for n≥7. In 2007 it was affirmed for n=6. The 1991 conjecture mentioned
above states that for every two integers n≥3 and q≥2, there exists an integer h(n,q) such that every set of h(n,q) points in the plane in
general position contains a subset of n
points which forms a convex n-gon,
where the number of points from the set which lie inside the convex n-gon is divisible by q. The authors proved the
conjecture under the assumption n≥q+2.
In 2001 Károlyi, Pach and Tóth proved the conjecture
under the assumption n≥(5/6)q+O(1).
Recently, among other results, Koshelev improved the upper bound on h(n,q), provided n≥2q-1.
We will survey related problems and results concerning points in the plane in general position along the lines outlined by Erdös. In addition we will try to incorporate some historical notes and folklore stories. The talk is suitable for mathematically mature audience as well as for undergraduate students.