You are here
Home ›Ramsey-theoretic proof of the Erd\H{o}s-Szekeres theorem
Primary tabs
Ramsey-theoretic proof of the Erdős-Szekeres theorem
Let be an integer. By the finite Ramsey theorem, there is a positive integer such that the arrows relation
holds. Let be a planar point set in general position with . Define a red-blue colouring of the triangles in as follows. Let be a triangle of with , , having monotonically increasing -coordinates. (If two points have the same -coordinate, break the tie by placing the point with smaller -coordinate first.) If lies above the line determined by and (the triangle “points up”), then colour the triangle blue. Otherwise, lies below the line (the triangle “points down”); in this case colour the triangle red.
Now there must be a homogeneous subset with . Without loss of generality, every triangle in is coloured blue. To see that this implies that the points of are the vertices of a convex -gon, suppose there exist , , , in such that and such that , , have monotonically increasing -coordinates (breaking ties as before). Since every triangle in is coloured blue, the triangle points up. If the -coordinate of is less than or equal to that of , then the triangle points down. But if the -coordinate of is greater than that of , the triangle points down. In either case there is a red triangle in the homogeneously blue , a contradiction. Hence is a convex -gon. This shows that .
References
- 1 P. Erdős and G. Szekeres, A combinatorial problem in geometry, 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.
Mathematics Subject Classification
05D10 Ramsey theory51D20 Combinatorial geometries
- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new question: Laplace transform by J
new question: Residue Calculus by J
May 19
new Education: Project: PlanetMath Outlines Series by unlord
May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden
new question: Solving the word problem for isomorphic groups by unlord
new image: LineDiagrams.jpg by m759
new image: ProjPoints.jpg by m759
new image: AbstrExample3.jpg by m759


