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

Let $n\geq 3$ be an integer. By the finite Ramsey theorem, there is a positive integer $N$ such that the arrows relation

 $N\to(n)^{3}_{2}$

holds. Let $X$ be a planar point set in general position with $|X|\geq 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|\geq 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\operatorname{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 $g(n)\leq N<\infty$.

## 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 RamseytheoreticProofOfTheErdHosSzekeresTheorem 2013-03-22 16:16:46 2013-03-22 16:16:46 mps (409) mps (409) 5 mps (409) Proof msc 05D10 msc 51D20