Ramsey-theoretic proof of the Erdős-Szekeres theorem
Let $n\ge 3$ be an integer. By the finite Ramsey theorem^{}, there is a positive integer $N$ such that the arrows relation
$$N\to {(n)}_{2}^{3}$$ |
holds. Let $X$ be a planar point set in general position with $|X|\ge N$. Define a red-blue colouring of the triangles^{} 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 $Y\subset X$ with $|Y|\ge 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 $d\in \mathrm{conv}\{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 contradiction^{}. Hence $Y$ is a convex $n$-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.
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 |