A combinatorial problem in geometry

A combinatorial problem in geometry

1935 | P. Erdős, G. Szekeres
The article "A Combinatorial Problem in Geometry" by P. Erdös and G. Szekeres, published in *Compositio Mathematica* in 1935, addresses a geometric combinatorial problem. The problem, initially suggested by Miss Esther Klein, asks whether for any set of at least \( N(n) \) points in the plane, it is possible to select \( n \) points that form a convex polygon. The authors provide two proofs to affirm the existence of such a number \( N(n) \) and give estimates for \( N(n) \). The first proof uses Ramsey's theorem, which states that in any graph with sufficiently many vertices, there exists a complete subgraph of a certain order. By applying this theorem to a specific combinatorial structure, the authors show that for any \( n \), there are enough points to form a convex polygon. However, the estimate obtained from this proof is quite large and not close to the true limit. The second proof is more geometric and combinatorial. It involves considering points in the first quadrant of the plane with monotonically increasing abscissae and analyzing the properties of their ordinates. The authors derive recurrence relations for the minimum number of points required to form either \( i \) monotonically increasing or \( k \) monotonically decreasing points. They also solve a similar problem involving distances between points on a straight line and extend these results to the convex \( n \)-gon problem. The second proof provides more accurate estimates for \( N(n) \) and shows that the limit is exact in some cases. The article concludes with a discussion on the exactness of the limits derived and references to related work, including a proof by D. König using his lemma on infinite sets.The article "A Combinatorial Problem in Geometry" by P. Erdös and G. Szekeres, published in *Compositio Mathematica* in 1935, addresses a geometric combinatorial problem. The problem, initially suggested by Miss Esther Klein, asks whether for any set of at least \( N(n) \) points in the plane, it is possible to select \( n \) points that form a convex polygon. The authors provide two proofs to affirm the existence of such a number \( N(n) \) and give estimates for \( N(n) \). The first proof uses Ramsey's theorem, which states that in any graph with sufficiently many vertices, there exists a complete subgraph of a certain order. By applying this theorem to a specific combinatorial structure, the authors show that for any \( n \), there are enough points to form a convex polygon. However, the estimate obtained from this proof is quite large and not close to the true limit. The second proof is more geometric and combinatorial. It involves considering points in the first quadrant of the plane with monotonically increasing abscissae and analyzing the properties of their ordinates. The authors derive recurrence relations for the minimum number of points required to form either \( i \) monotonically increasing or \( k \) monotonically decreasing points. They also solve a similar problem involving distances between points on a straight line and extend these results to the convex \( n \)-gon problem. The second proof provides more accurate estimates for \( N(n) \) and shows that the limit is exact in some cases. The article concludes with a discussion on the exactness of the limits derived and references to related work, including a proof by D. König using his lemma on infinite sets.
Reach us at info@study.space
[slides] A combinatorial problem in geometry | StudySpace