In mathematics, the "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein) is the following statement:

This was one of the original results that led to the development of Ramsey theory.

The happy ending theorem can be proven by a simple case analysis: if four or more points are vertices of the convex hull, any four such points can be chosen. If on the other hand, the convex hull has the form of a triangle with two points inside it, the two inner points and one of the triangle sides can be chosen. See  for an illustrated explanation of this proof, and  for a more detailed survey of the problem.

The Erdős–Szekeres conjecture states precisely a more general relationship between the number of points in a general-position point set and its largest subset forming a convex polygon, namely that the smallest number of points for which any general position arrangement contains a convex subset of  points is . It remains unproven, but less precise bounds are known.

Larger polygons

 proved the following generalisation:

The proof appeared in the same paper that proves the Erdős–Szekeres theorem on monotonic subsequences in sequences of numbers.

Let  denote the minimum  for which any set of  points in general position must contain a convex N-gon. It is known that
 , trivially.
 .
 . A set of eight points with no convex pentagon is shown in the illustration, demonstrating that ; the more difficult part of the proof is to show that every set of nine points in general position contains the vertices of a convex pentagon.
 .
 The value of  is unknown for all . By the result of ,  is known to be finite for all finite .

On the basis of the known values of  for N = 3, 4 and 5, Erdős and Szekeres conjectured in their original paper that 

They proved later, by constructing explicit examples, that
.
In 2016 Andrew Suk showed that for 

Suk actually proves, for N sufficiently large,  

A 2020 preprint by Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach and Gábor Tardos claims an improvement on Suk:

Empty convex polygons
There is also the question of whether any sufficiently large set of points in general position has an "empty" convex quadrilateral, pentagon, etc.,
that is, one that contains no other input point. The original solution to the happy ending problem can be adapted to show that any five points in general position have an empty convex quadrilateral, as shown in the illustration, and any ten points in general position have an empty convex pentagon. However, there exist arbitrarily large sets of points in general position that contain no empty convex heptagon.

For a long time the question of the existence of empty hexagons remained open, but  and  proved that every sufficiently large point set in general position contains a convex empty hexagon.  More specifically, Gerken showed that the number of points needed is no more than f(9) for the same function f defined above, while Nicolás showed that the number of points needed is no more than f(25).  supplies a simplification of Gerken's proof that however requires more points, f(15) instead of f(9). At least 30 points are needed; there exists a set of 29 points in general position with no empty convex hexagon.

Related problems
The problem of finding sets of n points minimizing the number of convex quadrilaterals is equivalent to minimizing the crossing number in a straight-line drawing of a complete graph. The number of quadrilaterals must be proportional to the fourth power of n, but the precise constant is not known.

It is straightforward to show that, in higher-dimensional Euclidean spaces, sufficiently large sets of points will have a subset of k points that forms the vertices of a convex polytope, for any k greater than the dimension: this follows immediately from existence of convex  in sufficiently large planar point sets, by projecting the higher-dimensional point set into an arbitrary two-dimensional subspace. However, the number of points necessary to find k points in convex position may be smaller in higher dimensions than it is in the plane, and it is possible to find subsets that are more highly constrained. In particular, in d dimensions, every d + 3 points in general position have a subset of d + 2 points that form the vertices of a cyclic polytope. More generally, for every d and k > d there exists a number m(d, k) such that every set of m(d, k) points in general position has a subset of k points that form the vertices of a neighborly polytope.

Notes

References

.
.
. Reprinted in: .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

External links
 Happy ending problem and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath

Discrete geometry
Euclidean plane geometry
Quadrilaterals
Polygons
Mathematical problems
Ramsey theory
Paul Erdős
해피 엔딩 문제()는 수학에서 다음 명제이다: 에르되시 팔이 이러한 이름을 명명하였는데, 정리를 증명한 세케레시 죄르지와 클라인 에스더의 결혼으로 이어졌기 때문이다. 이는 램지 이론의 발전으로 이어진 독창적인 결과 중 하나이다.

해피 엔딩 정리는 간단한 사례 분석으로 증명할 수 있다. 4개 이상의 점이 볼록 껍질의 꼭짓점인 경우 이러한 점 4개를 선택한다. 반면에 볼록 껍질이 내부에 두 개의 점이 있는 삼각형 형태인 경우 두 개의 내부 점과 삼각형의 모서리 중 하나를 선택할 수 있다. 이 증명에 대한 설명을 보려면  을 참조할 수 있다. 문제에 대한 보다 자세한 조사는 을 참조할 수 있다.

에르되시-세케레시 추측은 일반 위치 점 집합의 점 수와 가장 큰 볼록 다각형 사이의 보다 일반적인 관계를 정확하게 나타내는 다음 명제이다. 일반 위치에 있는 점 개의 집합은 볼록 각형을 포함한다. 에르되시-세케레시 추측은 증명되지 않은 채로 남아 있지만 덜 정확한 경계는 알려져 있다.

더 큰 다각형 

1935년 에르되시와 세케레시는 일반화된 다음 명제를 증명했다.

증명은 수열의 단조 부분 수열에 대한 에르되시–세케레시 정리를 증명하는 동일한 논문에 나타났다.

를 평면 위의 일반 위치에 있는 점 개의 집합이 볼록 각형을 포함해야 하는 최소 으로 표시하자. 이와 관해 다음 사실이 알려져 있다.

 . 이는 자명하다.
 .
 . 볼록 오각형이 없는 점 8개의 집합이 그림에 나와 있으며, 이는 임을 보여준다. 증명의 어려운 부분은 일반적인 위치에 있는 모든 9개의 점 집합이 볼록 오각형의 꼭짓점을 포함한다는 것을 밝히는 것이다.
 .
 의 값은 모든  에 대해 알려져 있지 않다. 의 결과에 따르면 는 모든 양의 정수 에 대해 유한하다.

N = 3, 4 및 5에 대해 알려진  값을 기반으로 에르되시와 세케레시는 원래 논문에서 다음과 추측했다: 모든 에 대해 이다.

그들은 나중에 명백한 예를 구성하여 을 증명했다.

일 때 알려진 가장 좋은 상한은 이다.

빈 볼록 다각형 
일반 위치에 있는 점들의 충분히 큰 집합이 집합의 다른 점을 포함하지 않는 "빈" 볼록 사각형, 오각형 등이 존재하는지 여부에 대한 질문을 할 수 있다. 해피 엔딩 문제에 대한 원래의 해는 그림과 같이 일반 위치에 있는 5개의 점이 비어 있는 볼록 사변형을 갖는다는 것을 나타내도록 적용될 수 있고, 모든 일반 위치에 있는 점 10개의 집합이 비어 있는 볼록 오각형을 갖는다. 그러나 빈 볼록 칠각형을 포함하지 않는 충분히 큰 일반 위치에 있는 점들의 집합이 존재한다.

오랫동안 빈 육각형의 존재에 대한 질문은 열려 있었지만,  와  은 임의의 충분히 큰 일반 위치에 있는 점들의 집합이 빈 볼록 육각형을 포함한다는 것을 증명했다. 보다 구체적으로, Gerken은 위에서 정의한 동일한 함수 f에 대해 필요한 포인트 수가 f(9) 이하임을 보였고 Nicolás는 필요한 점 수가 f (25) 이하임을 보였다. 은 Gerken의 증명을 단순화했지만 f(9) 대신 점 f(15)개로 점을 더 많이 요구한다. 최소한 점 30개가 필요한데, 빈 볼록 육각형이 없는 일반 위치의 점 29개의 집합이 존재한다.

관련 문제 
볼록 사각형의 수를 최소화하는 n개의 점 집합을 찾는 문제는 완전한 그래프의 직선 그리기에서 교차 수를 최소화하는 것과 같다. 사각형의 수는 n의 네제곱에 비례하지만 정확한 상수는 알려져 있지 않다.

고차원 유클리드 공간에서 충분히 큰 점 집합은 차원보다 큰 임의의 에 대해 볼록 다포체의 꼭짓점을 형성하는 점 개의 부분 집합을 가진다. 이는 고차원 점 집합을 임의의 2차원 부분 공간으로 투영함으로써, 충분히 큰 평면 점 집합에서 볼록 각형의 존재로부터 즉시 보여진다.  그러나 볼록 위치에 있는 개의 점을 찾는 데 필요한 점의 수는 평면에서보다 고차원에서 더 작을 수 있으며 더 많이 구속된 부분 집합을 찾는 것이 가능하다. 특히, 차원에서 모든 일반 위치에 있는 개의 점은 순환 다포체의 꼭짓점을 형성하는 점 개의 부분 집합을 갖는다. 보다 일반적으로 모든 인  및 에 대해 모든 일반 위치에 있는 점 개의 집합이 인접 다포체의 꼭짓점을 형성하는 점 개의 부분 집합을 갖도록 하는 수 가 존재한다.

각주

참고 문헌 

.
.
. Reprinted in: .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

외부 링크 

 PlanetMath에서 해피 엔딩 문제 및 Erdős-Szekeres 정리의 Ramsey 이론 증명
 
에르되시 팔
램지 이론
수학 문제
다각형
사각형
유클리드 평면 기하학
이산기하학