![[parent]](https://cdn.statically.io/img/web.archive.org/web/20060925032736im_/http://images.planetmath.org:8080/images/uparrow.png)
Ramsey-theoretic proof of the Erdős-Szekeres theorem
|
(Proof)
|
|
|
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
 .
- 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.
|
"Ramsey-theoretic proof of the Erdős-Szekeres theorem" is owned by mps.
|
|
(view preamble)
This object's parent.
Cross-references: contradiction, convex, vertices, implies, without loss of generality, subset, homogeneous, BLUE, colour, line, monotonically increasing, triangles, colouring, general position, point, planar, relation, arrows, positive, Ramsey theorem, integer
This is version 2 of Ramsey-theoretic proof of the Erdős-Szekeres theorem, born on 2006-09-22, modified 2006-09-22.
Object id is 8391, canonical name is RamseyTheoreticProofOfTheErdHosSzekeresTheorem.
Accessed 46 times total.
Classification:
| AMS MSC: | 51D20 (Geometry :: Geometric closure systems :: Combinatorial geometries) | | | 05D10 (Combinatorics :: Extremal combinatorics :: Ramsey theory) |
|
