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 .

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