Combinatorics (Fall 2010)/Ramsey theory

Ramsey's Theorem

Ramsey's Theorem

Let [math]\displaystyle{ r, s, k }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ N }[/math] with the following property: If [math]\displaystyle{ |X|\ge N }[/math] and [math]\displaystyle{ f:{X\choose r}\rightarrow[s] }[/math] is an arbitrary [math]\displaystyle{ s }[/math]-coloring of [math]\displaystyle{ {X\choose r} }[/math], then there exists a subset [math]\displaystyle{ Y\subseteq Y }[/math] with [math]\displaystyle{ Y\ge k }[/math] such that [math]\displaystyle{ {Y\choose r} }[/math] is monochromatic.

The "Happy Ending" problem

The happy ending problem

Any set of 5 points in the plane, no three on a line, has a subset of 4 points that form the vertices of a convex quadrilateral.

See the article [1] for the proof.

We say a set of points in the plane in general positions if no three of the points are on the same line.

Theorem (Erdős-Szekeres 1935)

For any positive integer [math]\displaystyle{ n\ge 3 }[/math], there is an [math]\displaystyle{ N(n) }[/math] such that any set of at least [math]\displaystyle{ N(n) }[/math] points in general position in the plane (i.e., no three of the points are on a line) contains [math]\displaystyle{ n }[/math] points that are the vertices of a convex [math]\displaystyle{ n }[/math]-gon.