ハッピーエンド問題

数学において、「ハッピーエンド問題」（ジョージ・シェケレスとエスター・クラインの結婚につながったことからポール・エルデシュによって名付けられた^[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}logN}.$

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

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

空の凸多角形

また、一般位置にある十分に大きな点の集合には、「空の」凸四辺形、五角形など、つまり他の入力点を含まないものが存在するかどうかという疑問もある。ハッピーエンド問題に対する元の解決法は、図に示すように、一般位置にある任意の 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).ここで使用されている表記法については二項係数とビッグオー表記法を、漸近展開についてはカタラン数またはスターリング近似を参照してください。
^ ホルムセンら（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の結果を適用することで得られます。

参考文献

チョン, FRK ;グラハム, 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、ケンブリッジ、マサチューセッツ州：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)、「Erdős–Szekeres 問題の 2 つの拡張」、Journal of the European Mathematical Society (JEMS)、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、vol. 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
Nicolás, Carlos 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 の定理に関する注記」、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 (編)、Combinatorial and Computational Geometry (PDF) 、Mathematical Sciences Research Institute Publications、vol. 52、Cambridge University Press、pp. 557–568、2019-07-28にオリジナル(PDF)からアーカイブ、 2015-02-28に取得
Valtr, P. (2008)、「空の六角形について」、Goodman, Jacob E. ; Pach, János ; Pollack, Richard (編)、離散幾何学と計算幾何学に関する調査: 20 年後: AMS-IMS-SIAM 合同夏季研究会議、2006 年 6 月 18 ～ 22 日、ユタ州スノーバード、Contemporary Mathematics、vol. 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] ホルムセンら（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の結果を適用することで得られます。

より大きなポリゴン

空の凸多角形

関連する問題

注記

参考文献

外部リンク