happy ending problem


May 29, 2022

In mathematics, the happy ending problem is the following proposition: Erdos Pal gave this name to the marriage of Sekeresi Gyorgi and Klein Esther, who proved the theorem. This is one of the original results that led to the development of Ramsey's theory. The happy ending theorem can be proved by a simple case analysis. If 4 or more points are vertices of a convex hull, select 4 of these points. On the other hand, if a convex hull is in the form of a triangle with two points inside, then we can choose one of the two inside points and the edge of the triangle. See Peterson (2000) for an explanation of this proof. For a more detailed investigation of the problem, see Morris & Soltan (2000). The Erdos-Sekeresi conjecture is the following proposition that accurately expresses the more general relationship between the number of points in a set of general location points and the largest convex polygon. point in normal location 2 n − 2 + One {\displaystyle 2^{n-2}+1} The set of dogs is convex n {\displaystyle n} Includes squares. The Erdos-Sekeresi conjecture remains unproven, but less precise boundaries are known.

Larger Polygons

In 1935, Erdossi and Sekeresi proved the following generalized proposition: The proof appeared in the same paper proving the Erdos-Sekeresi theorem for monotonic subsequences of sequences. Let f(N) be the set of M points in a general position on the plane is convex N {\displaystyle N} Let it be the minimum M that must contain the polygon. In this regard, the following is known: f(3) 3. This is self-evident. f(4) 5. f(5) 9. A set of 8 points without a convex pentagon is shown in the figure, showing that f(5) > 8. The difficult part of the proof is to prove that the set of all nine points in a general position contains the vertices of a convex pentagon. f(6) 17. The value of f(N) is unknown for all N > 6. According to the results of Erdős & Szekeres (1935), f(N) is finite for all positive integers N. Based on the known values ​​of f(N) for N 3, 4 and 5, Erdos and Szekeres were originally From the paper, I guessed: all N ≥ 3 {\displaystyle N\geq 3} About f ( N ) One + 2 N − 2 {\displaystyle f(N)1+2^{N-2}} to be. They later constituted an obvious example, f ( N ) ≥ One + 2 N − 2 {\displaystyle f(N)\geq 1+2^{N-2}} proved that the best known upper bound when N ≥ 7 is f ( N ) ≤ 2 N + o ( N ) {\textstyle f(N)\leq 2^{N+o(N)}} to be.

Empty Convex Polygon

One can ask the question whether there are "empty" convex quadrilaterals, pentagons, etc., where a sufficiently large set of points in a general position does not contain any other points in the set. The original solution to the happy ending problem is applied to indicate that five points in their normal positions have an empty convex quadrilateral as shown.