tailieunhanh - Báo cáo toán học: "Another abstraction of the Erd˝s-Szekeres o Happy End Theorem"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Another abstraction of the Erd˝s-Szekeres o Happy End Theorem. | Another abstraction of the Erdos-Szekeres Happy End Theorem Noga Alon Ehsan Chiniforooshan Vasek Chvatal Francois Genest Submitted Jul 13 2009 Accepted Jan 26 2010 Published Feb 8 2010 Mathematics Subject Classification 05D10 Abstract The Happy End Theorem of Erdos and Szekeres asserts that for every integer n greater than two there is an integer N such that every set of N points in general position in the plane includes the n vertices of a convex n-gon. We generalize this theorem in the framework of certain simple structures which we call happy end spaces . In the winter of 1932 33 Esther Klein observed that from any set of five points in the plane of which no three lie on the same line it is always possible to select four points that are vertices of a convex polygon. When she shared this news with a circle of her friends in Budapest the following prospect of generalizing it emerged Can we find for each integer n greater than two an integer N n such that from any set of N n points in the plane of which no three lie on the same line it is always possible to select n points that are vertices of a convex polygon Endre Makai proved that N 5 9 works here. A few weeks later George Szekeres proved the existence of N n for all n. His argument produced very large upper bounds for N n for instance it gave N 5 210000. Soon afterwards Paul Erdos came up with a different proof which led to much smaller values of N n Sackler School of Mathematics and Blavatnik School of Computer Sciences Tel Aviv University Tel Aviv Israel Department of Computer Science and Software Engineering Concordia University Montreal Quebec Canada Department of Computer Science and Software Engineering Concordia University Montreal Quebec Canada 5264 av. Henri-Julien app. 3 Montreal Quebec Canada THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N11 1 From any set of 2n_24 1 points in the plane of which no three lie on the same line it is always possible to select n points that are vertices of a convex .