快乐结局问题

Article

May 25, 2022

在数学中,幸福结局问题是以下命题:Erdos Pal 将这个名字命名为 Sekeresi Gyorgi 和 Klein Esther 的婚姻,后者证明了这个定理。这是导致拉姆齐理论发展的原始结果之一。快乐结局定理可以通过一个简单的案例分析来证明。如果 4 个或更多点是凸包的顶点,则选择其中 4 个点。另一方面,如果一个凸包是一个三角形的形式,里面有两个点,那么我们可以选择两个里面的点之一和三角形的边。有关此证明的解释,请参见 Peterson (2000)。有关该问题的更详细调查,请参阅 Morris & Soltan (2000)。Erdos-Sekeresi猜想是以下命题,它准确地表达了一组一般位置点中的点数与最大凸多边形之间的更一般的关系。一般位置的点 2 n − 2 + 1 {\displaystyle 2^{n-2}+1} 的集合包含一个凸的 n {\displaystyle n} 多边形。Erdos-Sekeresi 猜想仍未得到证实,但已知的边界不太精确。

更大的多边形

1935 年,Erdossi 和 Sekeresi 证明了以下广义命题:证明出现在同一篇论文中,该论文证明了序列单调子序列的 Erdos-Sekeresi 定理。设 f(N) 是平面上一般位置的 M 点集合必须包含凸 N {\displaystyle N} 多边形的最小 M。在这方面,以下是已知的:f(3) 3. 这是不言而喻的。f(4) 5. f(5) 9. 图中没有凸五边形的8个点的集合,可见f(5) > 8。证明的困难部分是证明在一个一般位置上的所有九个点的集合包含一个凸五边形的顶点。f(6) 17. 对于所有 N > 6,f(N) 的值是未知的。根据 Erdős & Szekeres (1935) 的结果,f(N) 对于所有正整数 N 都是有限的。基于已知的 N 3、4 和 5 的 f(N) 值,Erdos 和 Szekeres 在他们的原论文。从以下猜测:f ( N ) 1 + 2 N − 2 {\displaystyle f(N)1+2^{N-2}} 对于任何 N ≥ 3 {\displaystyle N\geq 3} 。他们后来构造了一个明确的例子来证明 f ( N ) ≥ 1 + 2 N − 2 {\displaystyle f(N)\geq 1+2^{N-2}} 。

空凸多边形

可以问是否存在“空”凸四边形、五边形等问题,其中在一般位置上足够大的一组点不包含该组中的任何其他点。可以应用快乐结局问题的原始解决方案来证明在一般位置的 5 个点具有如图所示的空凸四边形,并且在所有一般位置的 10 个点的集合具有如图所示的空凸五边形。然而,在足够大的一般位置上存在一组不包含空凸七边形的点。长期以来,空六边形是否存在的问题一直存在,但 Nicolás (2007) 和 Gerken (2008)已经发现任何足够大的一般位置我们证明了具有空凸六边形的点集包含。更具体地说,Gerken 表明上面定义的相同函数 f 所需的点数小于或等于 f(9),而 Nicolás 表明所需的点数小于或等于 f(25)。Valtr (2008) 简化了 Gerken 的证明,但使用 f(15) 而不是 f(9) 需要更多点。至少需要30个点,一般位置有一组29个点,没有空凸六边形。

相关问题

找到一组n个点以最小化凸矩形的数量的问题与最小化完整图形的直线中的交点数量相同。平方的数量与 n 的四次方成正比,但确切的常数是未知的。在高维欧几里得空间中足够大的一组点是一个点 k,它构成任何 k {\ displaystyle k} 大于它的维度。它有 {\displaystyle k} 子集。通过将一组高维点投影到任意二维子空间中,在足够大的平面点集合中存在凸 k {\displaystyle k} 多边形立即表明了这一点。然而,在凸位置上找到 k {\displaystyle k} 点所需的点数在更高维度上可能比在平面上要少,并且可以找到更受约束的子集。尤其,d + 3 {\displaystyle d+3} 点在维度 d {\displaystyle d} 的所有一般位置上都有 d + 2 {\displaystyle d+2} 点的子集,这些点形成了圆形多面体 的顶点。更一般地,点 m ( k , d ) {\displaystyle m(k,d) 对于 d {\displaystyle d} 和 k {\displaystyle k} 对于所有 k > d {\displaystyle k>d} )} 数 m ( k ,使得该集合具有 k {\displaystyle k} 点的子集,这些点形成了相邻的 polyphobe 的顶点)

脚注

参考

外部链接

Ramsey 在 PlanetMath Weisstein 中对快乐结局问题和 Erdős-Szekeres 定理的证明,Eric Wolfgang。“快乐结局问题”。Wolfram MathWorld(英语)。沃尔夫勒姆研究。