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