ハッピーエンドの問題

ハッピーエンド問題：一般位置にある5つの点の任意の組み合わせは、凸四角形の頂点を含む。

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

定理—平面上の一般位置にある任意の 5 つの点の集合^{[ 3 ]}は、凸四角形の頂点を形成する 4 つの点の部分集合を持つ。

これはラムゼー理論の発展につながった初期の成果の一つである。この問題は、最初にこの問題に取り組んだ2人の研究者、エステル・クラインとジョージ・セケレスが婚約し、後に結婚したことから、エルデシュによってそのように名付けられた（ホフマン 1998、p. 76）。

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

エルデシュ・セケレス予想は、一般位置点集合内の点の数と凸多角形を形成する最大の部分集合との間のより一般的な関係を正確に述べている。すなわち、任意の一般位置配置が凸部分集合を含む最小の点の数は、 $n$ ポイントは $2^n-2+1$ それはまだ証明されていないが、より大まかな範囲は知られている。

より大きな多角形

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

定理—任意の正の整数 $N$ に対して、平面上の一般位置にある十分大きな有限個の点の集合は、凸多角形の頂点を形成する $N個の点の部分集合を持つ。$

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

Let $f (N)$ denote the minimum $M$ for which any set of $M$ points in general position must contain a convex N-gon. It is known that

$f (3) = 3$ , trivially.
$f (4) = 5$ .^[4]
$f (5) = 9$ .^[5] A set of eight points with no convex pentagon is shown in the illustration, demonstrating that $f (5) > 8$ ; 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.
$f (6) = 17$ .^[6]
The value of $f (N)$ is unknown for all $N > 6$ . By the result of Erdős & Szekeres (1935), $f (N)$ is known to be finite for all finite $N$ .

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

凸六角形を含まない一般位置にある16個の点の集合 — A set of sixteen points in general position with no convex hexagon

$f(N)=1+2^{N-2}\quad {\text{すべての }}N\geq 3 に対して$ They proved later, by constructing explicit examples, that^[7] $f(N)\geq 1+2^{N-2}.$ In 2016 Andrew Suk^[8] showed that for $N \geq 7$ $f(N)\leq 2^{N+o(N)}.$

Suk actually proves, for N sufficiently large, $f(N)\leq 2^{N+6N^{2/3}\log N}.$

This was subsequently improved to:^[9]

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

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.^[10] However, there exist arbitrarily large sets of points in general position that contain no empty convex heptagon.^[11]

Let $N$ be the minimum number of points, such that any $N$ points in general position contains an empty hexagon. For a long time it is open whether $N$ exists. The question is now solved:

Overmars (2003) showed that if it exists, then $N\geq 30$ , by constructing an example with 29 points.
Nicolás (2007) showed that $N\leq f(25)$ .
ゲルケン（2008）は、 $N\leq f(9)$ 。
Valtr (2008)は Gerken (2008)のより単純だが緩やかなバージョンを作成し、 $N\leq f(15)$ 。
Heule & Scheucher (2024)は、SAT 解決アプローチを使用して、 $N=30$ 。