# 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

### 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_{1} and C_{2}, 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_{1}, or there exists a 5-element subset, B', of X such that every 4-element subset of B' belongs to C_{2}. 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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny