ハッピーエンド問題

5つの共面点は凸四辺形を形成する部分集合を持つ

数学において、「ハッピーエンド問題」（ジョージ・シェケレスとエスター・クラインの結婚につながったことからポール・エルデシュによって名付けられた^[1]）は次の命題である。

定理-一般的な位置^[2]にある平面上の5点の集合は、凸四辺形の頂点を形成する4点のサブセットを持ちます。

これはラムゼイ理論の発展につながった最初の結果の 1 つでした。

ハッピーエンド定理は、簡単な事例分析によって証明できます。凸包の頂点が4点以上ある場合、そのような点を任意に4つ選ぶことができます。一方、凸包が三角形で、その内部に2点がある場合、その三角形の内側の2点と1辺を選ぶことができます。この証明の図解付き説明についてはPeterson (2000)を、より詳細な問題についてはMorris & Soltan (2000)を参照してください。

エルデシュ＝シェケレス予想は、一般位置点集合内の点の数と、その凸多角形を形成する最大の部分集合との間の、より一般的な関係を正確に述べている。すなわち、任意の一般位置配置が点の凸部分集合を含む最小の点の数はである。これは未証明であるが、より厳密な境界値は知られている。 $n$ $2^{n-2}+1$

より大きなポリゴン

Erdős & Szekeres (1935) は次の一般化を証明しました。

定理-任意の正の整数 $N$ に対して、一般的な位置にある平面上の十分に大きい有限の点の集合には、凸多角形の頂点を形成する $N$ 点のサブセットが存在します。

この証明は、数列の単調部分列に関するエルデシュ・シェケレス定理を証明する同じ論文に掲載されました。

$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) の結果によれば、 $f (N)は有限の$ $N$ に対して常に有限であることが分かっている。

N = 3、4、5のときの $f (N)$ の既知の値に基づいて、エルデシュとシェケレスは原著論文で次のように推測した。

$f(N)=1+2^{N-2}\quad {\text{すべてのNに対して}}N\geq 3.$ 彼らは後に明示的な例を構築することで^[6] 2016年にアンドリュー・サック^[7] $は$ $N\geq7$ に対して $f(N)\geq 1+2^{N-2}.$ $f(N)\leq 2^{N+o(N)}.$

Sukは実際に、Nが十分に大きい場合、 $f(N)\leq 2^{N+6N^{2/3}\log N}.$

これはその後次のように改良された。^[8]

$f(N)\leq 2^{N+O({\sqrt {N\log N}})}.$

空の凸多角形

また、一般位置にある十分に大きな点の集合には、「空の」凸四辺形、凸五角形など、つまり他の入力点を含まない凸四辺形が存在するかどうかという問題もある。ハッピーエンド問題に対する元の解は、図に示すように、一般位置にある任意の5点には空の凸四辺形が存在し、一般位置にある任意の10点には空の凸五角形が存在することを示すように改変することができる。^{[9]しかし、一般位置にある任意の大きな点の集合には、空の凸七}角形が存在しない。^[10]

長い間、空六角形の存在の問題は未解決のままであったが、Nicolás (2007) と Gerken (2008) は、一般位置にある十分に大きな点の集合はすべて凸空六角形を含むことを証明した。より具体的には、Gerken は、上で定義した同じ関数fに対して必要な点の数はf (9) 以下であることを示し、Nicolás は、必要な点の数はf (25) 以下であることを示した。Valtr (2008) は、Gerken の証明を簡略化したが、f (9)ではなく f (15) というより多くの点が必要である。少なくとも 30 個の点が必要であり、一般位置では空凸六角形がない 29 個の点の集合が存在している。^[11]この問題は、最終的に Heule & Scheucher (2024) によって回答され、SAT 解決アプローチを使用して、確かに一般位置にある 30 個の点の集合はすべて空六角形を含むことが示された。

注記

^ 教えと数字の世界 - 2倍、マイケル・カウリング、シドニー・モーニング・ヘラルド、2005年11月7日、2014年9月4日引用
^ この文脈では、一般的な位置とは、2 つの点が一致せず、3 つの点が同一線上にないことを意味します。
^ これは元々の問題であり、エスター・クラインによって証明されました。
^ Erdős & Szekeres (1935) によれば、これは E. Makai によって最初に証明され、最初に公表された証明は Kalbfleisch、Kalbfleisch & Stanton (1970) に掲載されました。
^ これはSzekeres & Peters (2006)によって証明されました。彼らはコンピュータ探索を行い、凸六角形を含まない17点のあらゆる配置を除外し、すべての配置のうちごく一部だけを調べました。
^ エルデシュ＆シェケレス（1961）
^ Suk (2016).ここで使用されている表記法については二項係数とビッグオー記法を参照し、漸近展開についてはカタラン数またはスターリング近似を参照。
^ Holmsenら（2020年）。
^ ハーバース (1978).
^ ホートン（1983）
^ オーフェルマルス (2003).
^ シャイナーマン＆ウィルフ（1994）
^ Grünbaum (2003), Ex. 6.5.6, p.120. Grünbaumはこの結果をMicha A. Perlesの私信によるものとしている。
^ Grünbaum (2003), Ex. 7.3.6, p. 126. この結果は、Szekeresの元の証明に類似したRamsey理論的議論と、k = d + 2の場合のPerlesの結果を適用することで得られます。

参考文献

Chung, FRK ; Graham, RL (1998)、「平面における強制凸n角形」、離散幾何学と計算幾何学、19 (3): 367– 371、doi : 10.1007/PL00009353
エルデシュ、P. ; Szekeres, G. ( 1935)、「幾何学における組み合わせの問題」、Compositio Mathematica、2 : 463–470
エルデシュ、P. ; Szekeres、G. (1961)、「初等幾何学のいくつかの極値問題について」、Ann.大学科学。ブダペスト。エトヴェシュ宗派数学。、3～ 4：53～ 62; Erdős, P. (1973), Spencer, J. (ed.), The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, pp. 680– 689に再録
ゲルケン、トビアス（2008）「平面点集合における空凸六角形」離散幾何学と計算幾何学、39（1-3）：239-272、doi：10.1007/s00454-007-9018-x
グリュンバウム、ブランコ(2003)、カイベル、フォルカー。ヴィクトル・クレー; Ziegler、Günter M. (編)、Convex Polytopes、Graduate Texts in Mathematics、vol. 221 (第 2 版)、シュプリンガー版、ISBN 0-387-00424-6
Harborth、Heiko (1978)、「Konvexe Fünfecke in ebenen Punktmengen」、Elemente der Mathematik、33 ( 5): 116–118
Heule, Marijn JH; Scheucher, Manfred (2024)、「ハッピーエンド：30点の集合ごとに空の六角形」、Finkbeiner, Bernd; Kovács, Laura (編)、『システムの構築と分析のためのツールとアルゴリズム』、Lecture Notes in Computer Science、vol. 14570、Springer-Verlag、pp. 61– 80、arXiv : 2403.00737、doi : 10.1007/978-3-031-57246-3_5、ISBN 978-3-031-57245-6
ホルムセン、アンドレアス F.モハラド、ホセイン・ナッサジアン。Pach, ヤーノス; Tardos, Gábor (2020)、「エルデシュ – セーケレス問題の 2 つの拡張」、ヨーロッパ数学協会ジャーナル、22 (12): 3981–3995、arXiv : 1710.11415、doi :10.4171/jems/1000、MR 4176784
ホートン, JD (1983)、「空凸7角形を持たない集合」、カナダ数学速報、26 (4): 482– 484、doi : 10.4153/CMB-1983-077-8、S2CID 120267029
Kalbfleisch, JD; Kalbfleisch, JG ; Stanton, RG (1970)、「凸領域における組合せ問題」、Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing、Congressus Numerantium、第1巻、バトンルージュ、ルイジアナ州：ルイジアナ州立大学、pp. 180– 188
Kleitman, DJ ; Pachter, L. (1998)、「平面上の点間の凸集合の探索」、離散幾何学と計算幾何学、19 (3): 405– 410、doi : 10.1007/PL00009358
モリス, W.; ソルタン, V. (2000)「凸位置の点に関するエルデシュ・シェケレス問題—概観」アメリカ数学会報、37 (4): 437– 458, doi : 10.1090/S0273-0979-00-00877-6
ニコラス、カルロス・M.（2007）、「空六角形定理」、離散幾何学と計算幾何学、38（2）：389-397、doi：10.1007/s00454-007-1343-6
Overmars, M. (2003)、「空凸6角形を持たない点集合の探索」、離散幾何学と計算幾何学、29 (1): 153– 158、doi : 10.1007/s00454-002-2829-x
ピーターソン、イヴァース（2000年）「ブダペストの平面」、MAAオンライン、2013年7月2日時点のオリジナルよりアーカイブ
シャイナーマン、エドワード・R. ;ウィルフ、ハーバート・S. (1994)、「完全グラフの直線交差数とシルベスターの幾何学的確率の「4点問題」」アメリカ数学月刊誌、101 (10)、アメリカ数学会: 939– 943、doi :10.2307/2975158、JSTOR 2975158
Suk、Andrew (2016)、「エルデシュ – セーケレスの凸多角形問題について」、J. Amer。数学。社会、30 (4): 1047–1053、arXiv : 1604.08657、doi :10.1090/jams/869、S2CID 15732134
ゼケレス、G. ; Peters, L. (2006)、「17 点エルデシュ-セーケレス問題のコンピューターによる解決」、ANZIAM ジャーナル、48 (2): 151–164、doi : 10.1017/S144618110000300X
トート、G. Valtr, P. (1998)、「Erdős-Szekeres theorem に関する注記」、Discrete and Computational Geometry、19 (3): 457–459、doi : 10.1007/PL00009363
Tóth, G.; Valtr, P. (2005), 「エルデシュ・シェケレス定理：上限と関連結果」、Goodman, Jacob E. ; Pach, János ; Welzl, Emo (eds.), Combinatorial and Computational Geometry (PDF)、Mathematical Sciences Research Institute Publications、第52巻、Cambridge University Press、pp. 557– 568、2019年7月28日時点のオリジナル (PDF )からアーカイブ、2015年2月28日取得
Valtr, P. (2008)「空六角形について」、Goodman, Jacob E. ; Pach, János ; Pollack, Richard (編)、『離散幾何学と計算幾何学のサーベイ：20年後：AMS-IMS-SIAM合同夏季研究会議』、2006年6月18日～22日、ユタ州スノーバード、Contemporary Mathematics、第453巻、アメリカ数学会、pp. 433– 442、ISBN 9780821842393

外部リンク

PlanetMathにおけるハッピーエンド問題とエルデシュ・シェケレス定理のラムゼー理論的証明
ワイスタイン、エリック W.、「ハッピーエンド問題」、MathWorld

[1] 教えと数字の世界 - 2倍、マイケル・カウリング、シドニー・モーニング・ヘラルド、2005年11月7日、2014年9月4日引用

[2] この文脈では、一般的な位置とは、2 つの点が一致せず、3 つの点が同一線上にないことを意味します。

[3] これは元々の問題であり、エスター・クラインによって証明されました。

[4] Erdős & Szekeres (1935) によれば、これは E. Makai によって最初に証明され、最初に公表された証明は Kalbfleisch、Kalbfleisch & Stanton (1970) に掲載されました。

[5] これはSzekeres & Peters (2006)によって証明されました。彼らはコンピュータ探索を行い、凸六角形を含まない17点のあらゆる配置を除外し、すべての配置のうちごく一部だけを調べました。

[6] エルデシュ＆シェケレス（1961）

[7] Suk (2016).ここで使用されている表記法については二項係数とビッグオー記法を参照し、漸近展開についてはカタラン数またはスターリング近似を参照。

[FOOTNOTEHolmsenMojarradPachTardos2020-8] Holmsenら（2020年）。

[9] ハーバース (1978).

[10] ホートン（1983）

[11] オーフェルマルス (2003).

[12] シャイナーマン＆ウィルフ（1994）

[13] Grünbaum (2003), Ex. 6.5.6, p.120. Grünbaumはこの結果をMicha A. Perlesの私信によるものとしている。

[14] Grünbaum (2003), Ex. 7.3.6, p. 126. この結果は、Szekeresの元の証明に類似したRamsey理論的議論と、k = d + 2の場合のPerlesの結果を適用することで得られます。

ハッピーエンド問題

より大きなポリゴン

空の凸多角形

関連する問題

注記

参考文献

外部リンク