Combinatorics (Fall 2010)/Ramsey theory: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
Line 8: | Line 8: | ||
See the article | See the article | ||
[http://www.maa.org/mathland/mathtrek_10_3_00.html] for the proof. | [http://www.maa.org/mathland/mathtrek_10_3_00.html] for the proof. | ||
We say | |||
{{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 | :For any positive integer <math>n\ge 3</math>, there is an <math>N(n)</math> such that any set of at least <math>N(n)</math> points in general position in the plane (i.e., no three of the points are on a line) contains <math>n</math> points that are the vertices of a convex <math>n</math>-gon. | ||
}} | }} | ||
Revision as of 08:57, 17 November 2010
Ramsey's Theorem
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
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.