Ramsey-theoretic proof of the Erdős-Szekeres theorem

Let n3 be an integer. By the finite Ramsey theoremMathworldPlanetmath, there is a positive integer N such that the arrows relation


holds. Let X be a planar point set in general position with |X|N. Define a red-blue colouring of the trianglesMathworldPlanetmath in X as follows. Let T={a,b,c} be a triangle of X with a, b, c having monotonically increasing x-coordinates. (If two points have the same x-coordinate, break the tie by placing the point with smaller y-coordinate first.) If b lies above the line determined by a and c (the triangle “points up”), then colour the triangle blue. Otherwise, b lies below the line (the triangle “points down”); in this case colour the triangle red.

Now there must be a homogeneous subset YX with |Y|n. Without loss of generality, every triangle in Y is coloured blue. To see that this implies that the points of Y are the vertices of a convex n-gon, suppose there exist a, b, c, d in Y such that dconv{a,b,c} and such that a, b, c have monotonically increasing x-coordinates (breaking ties as before). Since every triangle in Y is coloured blue, the triangle {a,b,c} points up. If the x-coordinate of d is less than or equal to that of b, then the triangle {a,d,b} points down. But if the x-coordinate of d is greater than that of b, the triangle {b,d,c} points down. In either case there is a red triangle in the homogeneously blue Y, a contradictionMathworldPlanetmathPlanetmath. Hence Y is a convex n-gon. This shows that g(n)N<.


  • 1 P. Erdős and G. Szekeres, A combinatorial problem in geometryMathworldPlanetmath, Compositio Math. 2 (1935), 463–470.
  • 2 W. Morris and V. Soltan, The Erdős–Szekeres problem on points in convex position – a survey, Bull. Amer. Math. Soc. 37 (2000), 437–458.
Title Ramsey-theoretic proof of the Erdős-Szekeres theorem
Canonical name RamseytheoreticProofOfTheErdHosSzekeresTheorem
Date of creation 2013-03-22 16:16:46
Last modified on 2013-03-22 16:16:46
Owner mps (409)
Last modified by mps (409)
Numerical id 5
Author mps (409)
Entry type Proof
Classification msc 05D10
Classification msc 51D20