Combinatorics (Fall 2010)/Ramsey theory
Ramsey's Theorem
Ramsey's Theorem (graph, multicolor) - Let [math]\displaystyle{ s, k_1,k_2,\ldots,k_s }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ N }[/math] satisfying:
- For any [math]\displaystyle{ s }[/math]-coloring of a complete graph of at least [math]\displaystyle{ N }[/math] vertices, there exists a monochromatic [math]\displaystyle{ k_i }[/math]-clique with the [math]\displaystyle{ i }[/math]th color for some [math]\displaystyle{ i\in{1,2,\ldots,s} }[/math].
Ramsey's Theorem (hypergraph, multicolor, diagonal case) - Let [math]\displaystyle{ r, s, k }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ N }[/math] satisfying:
- For any [math]\displaystyle{ s }[/math]-coloring of [math]\displaystyle{ {[n]\choose r} }[/math] with [math]\displaystyle{ n\ge N }[/math], there exists a subset [math]\displaystyle{ X\subseteq [n] }[/math] with [math]\displaystyle{ |X|\ge k }[/math] such that [math]\displaystyle{ {Y\choose r} }[/math] is monochromatic.
Ramsey's Theorem (hypergraph, multicolor, general case) - 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] satisfying:
- For any [math]\displaystyle{ s }[/math]-coloring of [math]\displaystyle{ {[n]\choose r} }[/math] with [math]\displaystyle{ n\ge N }[/math], there exist an [math]\displaystyle{ i\in\{1,2,\ldots,s\} }[/math] and a subset [math]\displaystyle{ X\subseteq [n] }[/math] with [math]\displaystyle{ |X|\ge k_i }[/math] such that all members of [math]\displaystyle{ {Y\choose r} }[/math] are colored with the [math]\displaystyle{ i }[/math]the color.
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.