Combinatorics (Fall 2010)/Ramsey theory: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
Line 3: | Line 3: | ||
=== The "Happy Ending" problem === | === The "Happy Ending" problem === | ||
{{Theorem|The happy ending problem| | |||
:Any set of 5 points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral. | |||
}} | |||
{{Theorem|Theorem (Erdős-Szekeres 1935)| | {{Theorem|Theorem (Erdős-Szekeres 1935)| | ||
:For any positive integer <math>n\ge 3</math>, there is an <math>N(n)</math> such that any collection of <math>N\ge N(n)</math> points in the Euclidian plane, no three of which are collinear, has a subset of <math>n</math> points forming a convex <math>n</math>-gon. | :For any positive integer <math>n\ge 3</math>, there is an <math>N(n)</math> such that any collection of <math>N\ge N(n)</math> points in the Euclidian plane, no three of which are collinear, has a subset of <math>n</math> points forming a convex <math>n</math>-gon. |
Revision as of 08:16, 17 November 2010
Ramsey's Theorem
Ramsey number
The "Happy Ending" problem
The happy ending problem - Any set of 5 points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral.
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 collection of [math]\displaystyle{ N\ge N(n) }[/math] points in the Euclidian plane, no three of which are collinear, has a subset of [math]\displaystyle{ n }[/math] points forming a convex [math]\displaystyle{ n }[/math]-gon.