## You are here

HomeRamsey-theoretic proof of the Erd\H{o}s-Szekeres theorem

## Primary tabs

# 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\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.

## Mathematics Subject Classification

05D10*no label found*51D20

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prime numbers out of sequence by Rubens373

Oct 7

new question: Lorenz system by David Bankom

Oct 19

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag