Department of Mathematics Colloquium

University of Idaho

Fall 2011
Thursday,  December 8, 3:30-4:20pm, room TLC 030

Refreshments in Brink 305 at 3:00 p.m.

On Points in the Plane in General Position

 

Arie Bialostocki


Department of Mathematics

University of Idaho



Abstract

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 q2, 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.