A Geometric Application of Ramsey's Theory
The goal of this page is to prove the following
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.
For any 5 points in the plane in general position, some 4 of them are the vertices of a convex quadrilateral.
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
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.
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, C1 and C2, 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 C1, or there exists a 5-element subset, B', of X such that every 4-element subset of B' belongs to C2. The latter alternative is impossible, by Lemma 1. The former alternative must then hold; and Lemma 2 at once gives the proof.
- V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995, p. 25
Copyright © 1996-2018 Alexander Bogomolny