해피엔딩 문제

해피엔딩 문제: 일반적인 위치의 5개 지점 세트마다 볼록한 사각형의 정점을 포함한다.

수학에서 "해피엔딩 문제"(George Szekeres와 Esther Klein의^[1] 결혼으로 이어졌기 때문에 폴 에르드스가 그렇게 이름 지었다)는 말은 다음과 같다.

정리 — 평면에서 일반적인^[2] 위치에 있는 5개의 점 집합에는 볼록한 사각형의 정점을 이루는 4개의 점의 부분집합이 있다.

이것은 램지 이론의 발전을 이끈 최초의 결과 중 하나였다.

해피엔딩 정리는 단순한 케이스 분석으로 증명할 수 있는데, 4개 이상의 포인트가 볼록한 선체의 정점일 경우, 그러한 포인트 4개를 선택할 수 있다.반면 볼록한 선체는 내부에 2개의 점이 있는 삼각형의 형태를 가지고 있다면, 안쪽의 2개의 점과 삼각형의 1개의 면을 선택할 수 있다.이 증명에 대한 자세한 설명은 피터슨(2000)을 참조하고, 문제에 대한 자세한 조사는 모리스 & 솔탄(2000)을 참조한다.

Erdős-Szekeres 추측에 따르면 일반 위치 집합의 점 수와 가장 큰 볼록 폴리곤 사이의 보다 일반적인 관계가 정밀하게 설명되며, 즉 $일반$ 위치 배치가 n ${\displaystyn}$ 포인트의 $n$ 볼록 부분 집합을 포함하는 점의 최소 수는 $2^{n-2}+1$ - $2^{n-2}+1$ + 1 ${\displays$ }이다. $스타일$ 2 $^{n-2}+1$ } $.$ 아직 검증되지 않은 상태지만 정확도가 떨어지는 한계가 알려져 있다.

큰 다각형

볼록한 펜타곤이 없는 일반 위치의 8점 세트

Erdős & Szekeres(1935년)는 다음과 같은 일반화를 증명했다.

정리 - 임의의 양의 $정수$ N에 대해, 일반 위치의 평면에 충분히 큰 유한한 점 집합에는 볼록 폴리곤의 정점을 $형성$ 하는 N 점의 부분집합이 있다.

그 증거는 숫자의 순서에서 단조로운 반복에 대한 Erdős-Szekeres의 정리를 증명하는 동일한 논문에서 나타났다.

$f (N)$ 는 일반 위치의 $M$ 지점 세트가 볼록한 N-곤을 포함해야 하는 최소 $M$ 을 나타낸다.라고 알려져 있다.

$f (3)$ = 3, $사소한$ 것.
$f (4) = 5$ .^[3]
$f (5)$ = $9$ .^[4] 그림에는 볼록한 펜타곤이 없는 8개의 점 세트가 나타나 있는데, $f$ (5) > $8$ 을 증명한다. 일반적인 위치에 있는 9개의 점 세트마다 볼록한 펜타곤의 정점을 포함하고 있다는 것을 증명하는 것이 더 어려운 부분이다.
$f (6) = 17$ .^[5]
$f (N)$ 의 값은 $모든$ N > $6$ 에 대해 알 수 없다. Erdős & Szekeres(1935)의 결과에 의해 유한하다고 알려져 있다.

N = 3, 4, 5에 대해 $알려진$ f $(N)$ 값을 기초로 Erdds와 Szekeres는 원래 논문에서 다음과 같이 추측했다.

f(N)=1+2^{{N-2}\quad {\text{모든 }}

그들은 나중에, 명시적인 예를 구성함으로써, 그것을^[6] 증명했다.

f(N)\geq 1+2^{N-2}

N

≥

7일

때 가장 잘 알려진 상한은^[7]

f(N)\leq 2^{N+o(N)}

빈 볼록 폴리곤

또한 일반적 위치에서 충분히 큰 점 집합이 "빈" 볼록한 사각형, 오각형 등, 즉 다른 입력점을 포함하지 않는 것을 가지는지에 대한 문제도 있다.해피엔딩 문제에 대한 원래의 해결책은 그림에서 보듯이 일반 위치의 어떤 5개 지점에도 빈 볼록한 사각형이 있고, 일반 위치의 어떤 10개 지점에도 빈 볼록한 볼록한 오각형이 있다는 것을 보여주도록 적응될 수 있다.^[8]그러나, 빈 볼록한 헵타곤을 포함하지 않는 일반적 위치에는 임의로 큰 점 집합이 존재한다.^[9]

오랫동안 비어 있는 육각형의 존재에 대한 의문이 열려 있었지만 니콜라스(2007)와 게르켄(2008)은 일반 위치에 설정된 모든 충분히 큰 점에는 볼록한 빈 육각형이 들어 있음을 증명했다.좀 더 구체적으로, 게르켄은 위에서 정의한 동일한 함수 f에 대해 필요한 포인트 수가 f(9) 이하임을, 니콜라스는 필요한 포인트 수가 f(25) 이하임을 보여주었다.발트르(2008)는 그러나 f(9)가 아닌 f(15)가 더 많은 포인트가 필요하다는 게르켄의 증거를 단순화한다.최소 30점 이상의 포인트가 필요하며, 빈 볼록 육각형이 없는 일반 포지션 29점 세트가 존재한다.^[10]

메모들

^ 교직과 숫자의 세계 - 두 번째, 2005년-11-07년 시드니 모닝헤럴드, 마이클 코울링이 2014-09-04년을 인용했다.
^ 이런 맥락에서 일반적 위치는 두 점이 일치하지 않고 세 점이 공선되지 않는다는 것을 의미한다.
^ 이것이 에스더 클라인에 의해 증명된 원래의 문제였다.
^ Erdős & Szekeres (1935년)에 따르면, 이것은 E. Makai에 의해 처음 증명되었다; 최초의 출판된 증거는 Kalbfleisch, Kalbfleisch & Stanton (1970년)에 나타났다.
^ 이것은 Szekeres & Peters(2006)에 의해 증명되었다.그들은 모든 구성 중 극히 일부만을 조사하면서 볼록한 육각형 없이 17개의 가능한 모든 구성을 제거하는 컴퓨터 검색을 수행했다.
^ 에르드데스 & 세케레스 (1961년)
^ 석모(2016년).여기서 사용되는 표기법은 이항계수와 큰 O 표기법을 참조하고, 카탈로니아 숫자 또는 스털링의 점증확장 근사치를 참조한다.
^ 하버스(1978년).
^ 호튼 (1983년)
^ 오버마르스(2003년).
^ 스키너맨 & 윌프(1994)
^ 그룬바움(2003, Ex. 6.5.6, 페이지 120).Grünbaum은 이 결과를 Micha A의 사적인 의사소통 탓으로 돌린다.펄스.
^ 그룬바움(2003, Ex. 7.3.6, 페이지 126).이 결과는 케이스 k = d + 2에 대한 Perles의 결과와 함께 Szekeres의 원본 증명과 유사한 Ramsey-theric 주장을 적용함으로써 나타난다.

참조

Chung, F.R.K.; Graham, R.L. (1998), "Forced convex n-gons in the plane", Discrete and Computational Geometry, 19 (3): 367–371, doi:10.1007/PL00009353.
Erdős, P.; Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Mathematica, 2: 463–470.
Erdős, P.; Szekeres, G. (1961), "On some extremum problems in elementary geometry", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3–4: 53–62. 재인쇄: .
Gerken, Tobias (2008), "Empty convex hexagons in planar point sets", Discrete and Computational Geometry, 39 (1–3): 239–272, doi:10.1007/s00454-007-9018-x.
Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M. (eds.), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, ISBN 0-387-00424-6.
Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elemente der Mathematik, 33 (5): 116–118.
Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26 (4): 482–484, doi:10.4153/CMB-1983-077-8.
Kalbfleisch, J.D.; Kalbfleisch, J.G.; Stanton, R.G. (1970), "A combinatorial problem on convex regions", Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 1, Baton Rouge, La.: Louisiana State Univ., pp. 180–188.
Kleitman, D.J.; Pachter, L. (1998), "Finding convex sets among points in the plane" (PDF), Discrete and Computational Geometry, 19 (3): 405–410, doi:10.1007/PL00009358.
Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", Bulletin of the American Mathematical Society, 37 (4): 437–458, doi:10.1090/S0273-0979-00-00877-6.
Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete and Computational Geometry, 38 (2): 389–397, doi:10.1007/s00454-007-1343-6.
Overmars, M. (2003), "Finding sets of points without empty convex 6-gons", Discrete and Computational Geometry, 29 (1): 153–158, doi:10.1007/s00454-002-2829-x.
Peterson, Ivars (2000), "Planes of Budapest", MAA Online, archived from the original on 2013-07-02.
Scheinerman, Edward R.; Wilf, Herbert S. (1994), "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability", American Mathematical Monthly, Mathematical Association of America, 101 (10): 939–943, doi:10.2307/2975158, JSTOR 2975158.
Suk, Andrew (2016), "On the Erdős–Szekeres convex polygon problem", J. Amer. Math. Soc., 30 (4): 1047–1053, arXiv:1604.08657, doi:10.1090/jams/869, S2CID 15732134.
Szekeres, G.; Peters, L. (2006), "Computer solution to the 17-point Erdős-Szekeres problem", ANZIAM Journal, 48 (2): 151–164, doi:10.1017/S144618110000300X.
Tóth, G.; Valtr, P. (1998), "Note on the Erdős-Szekeres theorem", Discrete and Computational Geometry, 19 (3): 457–459, doi:10.1007/PL00009363.
Tóth, G.; Valtr, P. (2005), "The Erdős-Szekeres theorem: upper bounds and related results", in Goodman, Jacob E.; Pach, János; Welzl, Emo (eds.), Combinatorial and Computational Geometry (PDF), Mathematical Sciences Research Institute Publications, vol. 52, Cambridge University Press, pp. 557–568.
Valtr, P. (2008), "On empty hexagons", in Goodman, Jacob E.; Pach, János; Pollack, Richard (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, June 18-22, 2006, Snowbird, Utah, Contemporary Mathematics, vol. 453, American Mathematical Society, pp. 433–442, ISBN 9780821842393.

외부 링크

[1] 교직과 숫자의 세계 - 두 번째, 2005년-11-07년 시드니 모닝헤럴드, 마이클 코울링이 2014-09-04년을 인용했다.

[2] 이런 맥락에서 일반적 위치는 두 점이 일치하지 않고 세 점이 공선되지 않는다는 것을 의미한다.

[3] 이것이 에스더 클라인에 의해 증명된 원래의 문제였다.

[4] Erdős & Szekeres (1935년)에 따르면, 이것은 E. Makai에 의해 처음 증명되었다; 최초의 출판된 증거는 Kalbfleisch, Kalbfleisch & Stanton (1970년)에 나타났다.

[5] 이것은 Szekeres & Peters(2006)에 의해 증명되었다.그들은 모든 구성 중 극히 일부만을 조사하면서 볼록한 육각형 없이 17개의 가능한 모든 구성을 제거하는 컴퓨터 검색을 수행했다.

[6] 에르드데스 & 세케레스 (1961년)

[7] 석모(2016년).여기서 사용되는 표기법은 이항계수와 큰 O 표기법을 참조하고, 카탈로니아 숫자 또는 스털링의 점증확장 근사치를 참조한다.

[8] 하버스(1978년).

[9] 호튼 (1983년)

[10] 오버마르스(2003년).

[11] 스키너맨 & 윌프(1994)

[12] 그룬바움(2003, Ex. 6.5.6, 페이지 120).Grünbaum은 이 결과를 Micha A의 사적인 의사소통 탓으로 돌린다.펄스.

[13] 그룬바움(2003, Ex. 7.3.6, 페이지 126).이 결과는 케이스 k = d + 2에 대한 Perles의 결과와 함께 Szekeres의 원본 증명과 유사한 Ramsey-theric 주장을 적용함으로써 나타난다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Search

해피엔딩 문제

네임스페이스

더

목차

큰 다각형

빈 볼록 폴리곤

관련 문제

메모들

참조

외부 링크