Ramsey-theoretic proof of the Erdős-Szekeres theorem
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 .
- 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.
|Title||Ramsey-theoretic proof of the Erdős-Szekeres theorem|
|Date of creation||2013-03-22 16:16:46|
|Last modified on||2013-03-22 16:16:46|
|Last modified by||mps (409)|