해피 엔딩 문제

해피 엔딩 문제: 일반적인 위치에 있는 다섯 점의 모든 집합은 볼록 사변형의 꼭짓점을 포함한다.

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

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

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

더 큰 다각형

볼록 오각형이 없는 일반적인 위치에 있는 8개의 점 집합

1935년 에르되시와 세케레시는 일반화된 다음 명제를 증명했다. 틀:수학 정리 증명은 수열의 단조 부분 수열에 대한 에르되시–세케레시 정리를 증명하는 동일한 논문에 나타났다.

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

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

N = 3, 4 및 5에 대해 알려진 틀:수학 값을 기반으로 에르되시와 세케레시는 원래 논문에서 다음과 추측했다: 모든 $N\ge 3$에 대해 $f(N)=1+2^{N-2}$이다.

그들은 나중에 명백한 예를 구성하여 $f(N)\ge 1+2^{N-2}$을 증명했다.

틀:수학일 때 알려진 가장 좋은 상한은 $f(N)\le 2^{N+o(N)}$이다.

빈 볼록 다각형

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

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

관련 문제

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

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

참고 문헌

• 틀:인용.
• 틀:인용.
• 틀:인용. Reprinted in: 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.
• 틀:인용.

외부 링크

• PlanetMath에서 해피 엔딩 문제 및 Erdős-Szekeres 정리의 Ramsey 이론 증명
• 틀:매스월드