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

References

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

  1. Ramsey's Theorem
  2. Party Acquaintances
  3. Ramsey Number R(3, 3, 3)
  4. Ramsey Number R(4, 3)
  5. Ramsey Number R(5, 3)
  6. Ramsey Number R(4, 4)
  7. Geometric Application of Ramsey's Theory
  8. Coloring Points in the Plane and Elsewhere
  9. Two Colors - Two Points
  10. Three Colors - Two Points
  11. Two Colors - All Distances
  12. Two Colors on a Straight Line
  13. Two Colors - Three Points
  14. Three Colors - Bichromatic Lines
  15. Chromatic Number of the Plane
  16. Monochromatic Rectangle in a 2-coloring of the Plane
  17. Two Colors - Three Points on Circle
  18. Coloring a Graph
  19. No Equilateral Triangles, Please

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

Copyright © 1996-2017 Alexander Bogomolny

 62683441

Search by google: