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\{1,2,\ldots,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 X }[/math] with [math]\displaystyle{ |Y|\ge k }[/math] such that [math]\displaystyle{ {Y\choose r} }[/math] is monochromatic.

Ramsey's Theorem

Let [math]\displaystyle{ r, s, k_1,k_2,\ldots,k_s }[/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\{1,2,\ldots,s\} }[/math] is an arbitrary [math]\displaystyle{ s }[/math]-coloring of [math]\displaystyle{ {X\choose r} }[/math], then there exist an [math]\displaystyle{ i\in\{1,2,\ldots,s\} }[/math] and a subset [math]\displaystyle{ Y\subseteq X }[/math] with [math]\displaystyle{ |Y|\ge k_i }[/math] such that all members of [math]\displaystyle{ {Y\choose r} }[/math] are colored with the [math]\displaystyle{ i }[/math]th color by [math]\displaystyle{ f }[/math].

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.