A Geometric Application of Ramsey's Theory

The goal of this page is to prove the following

Theorem

Show that for any integer m ≥ 3 there exists an integer n such that whenever n points in the plane are in general position, some m of these points are the vertices of a convex m-gon.

A collection of points in the plane are in general position if no 3 of the points are collinear. A polygon with n sides, or n-gon, is convex if the line segment joining any 2 interior points is also within the n-gon.

The proof below is based on two lemmas.

Lemma 1

For any 5 points in the plane in general position, some 4 of them are the vertices of a convex quadrilateral.

Proof

Let the smallest convex polygon that contains the 5 points be a convex m-gon; obviously, all the vertices of this m-gon belong to the given set of points. If m = 5 or m = 4, there is nothing to prove. If m = 3 (the only other possibility), there is a triangle formed by 3 of the 5 points (say, A, B, and C), and the other 2 points, D and E, are inside the triangle. Then the line determined by D and E will divide the triangle into 2 parts such that I of these 2 parts contains 2 vertices of the triangle (say, A and B); ABDE is the sought convex quadrilateral.

Lemma 2

If n points are located in general position in the plane, and if every quadrilateral formed from these n points is convex, then the n points are the vertices of a convex n-gon.

Proof

Suppose the n points do not form a convex n-gon. Consider the smallest convex polygon that contains the n points. At least one of the n points (say, the point P) is in the interior of this polygon. Let Q be one of the vertices of the polygon. Divide the polygon into triangles by drawing line segments joining Q to every vertex of the polygon. The point P then will be in the interior of one of these triangles, which contradicts the convexity hypothesis.

Proof of Theorem

Let n ≥ R(5, m; 4) and let X be any set of n points in general position. The class C of all 4-element subsets of X is partitioned into 2 subclasses, C₁ and C₂, the former being the subclass of quartets of points which determine convex quadrilaterals. Now, according to Ramsey's theorem, there exists an rn-element subset, B, of X such that every 4-element subset of B belongs to C₁, or there exists a 5-element subset, B', of X such that every 4-element subset of B' belongs to C₂. The latter alternative is impossible, by Lemma 1. The former alternative must then hold; and Lemma 2 at once gives the proof.

References

V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995, p. 25

41162539