# 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

- Ramsey's Theorem
- Party Acquaintances
- Ramsey Number R(3, 3, 3)
- Ramsey Number R(4, 3)
- Ramsey Number R(5, 3)
- Ramsey Number R(4, 4)
- Geometric Application of Ramsey's Theory
- Coloring Points in the Plane and Elsewhere
- Two Colors - Two Points
- Three Colors - Two Points
- Two Colors - All Distances
- Two Colors on a Straight Line
- Two Colors - Three Points
- Three Colors - Bichromatic Lines
- Chromatic Number of the Plane
- Monochromatic Rectangle in a 2-coloring of the Plane
- Two Colors - Three Points on Circle
- Coloring a Graph
- No Equilateral Triangles, Please

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

Copyright © 1996-2017 Alexander Bogomolny

62683441 |