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].
Ramsey number
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.