幸福结局问题

幸福结局问题（由保罗·埃尔德什命名，因为这个问题令乔治·塞凯赖什和爱丝特·克莱共谐连理）是问，在平面上，给定一般位置（即平面上任意三点不共线）上的多少点，才令其中必可以找到$n$点能组成凸$n$边形？

幸福结局问题：任何五个点中一定存在四个点组成凸四边形。

1935年，埃尔德什和塞凯赖什证明：给定任意正整数$N$，存在正整数$M$使得给定在平面上一般位置上的$M$点，其中必可以找到$N$点能组成凸$N$边形。

将$f(N)$表示为$M$的最小可能值，已知

• $f(3)=3$：显然易见
• $f(4)=5$ ：爱丝特·克莱证明；这就是最初的问题
• $f(5)=9$ ：埃尔德什和塞凯赖什表示E. Makai证明了这点，但首个印刷出来的证明则在1970年出现在Kalbfleisch et al
• $f(6)=17$：由塞凯赖什和Lindsay Peters以机器证明所有可能性。

1961年，埃尔德什和塞凯赖什证明 $f(N)\geq 1+2^{N-2}$。

1998年，一连三篇关于对$f(N)$的上界的文章被发表，其中最好的结果是由Tóth和Valtr找到的：

$f(N)\leq {2n-5 \choose n-3}+2$

2005年，他们进一步将此上界降低了1：

$f(N)\leq {2n-5 \choose n-3}+1$

2016年，Andrew Suk证明了：

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

参考

• Erdős, P., Szekeres, G., A combinatorial problem in geometry, Compositio Math. 2 (1935), 463--470.
• Erdős P., Szekeres G., On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3-4 (1961), 53–62. Reprinted in: Paul Erdős: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 680–689, MIT Press, Cambridge, MA, 1973.
• Kalbfleisch J.D., Kalbfleisch J.G., Stanton R.G., A combinatorial problem on convex regions, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La, 1970. Congr. Numer. 1 (1970), 180-188.
• Morris, W., and V. Soltan. 2000. The Erdös-Szekeres problem on points in convex position--A survey. Bulletin of the American Mathematical Society 37(October): 437.
• Tóth G., Valtr P., Note on the Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457–459.

外部链接

• 从鸽笼原理到幸福结局问题，台湾大学数学系 张镇华 （繁体中文）