万维百科

幸福结局问题

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

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

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

表示为的最小可能值,已知

  • :显然易见
  • :爱丝特·克莱证明;这就是最初的问题
  • :埃尔德什和塞凯赖什表示E. Makai证明了这点,但首个印刷出来的证明则在1970年出现在Kalbfleisch et al
  • :由塞凯赖什和Lindsay Peters以机器证明所有可能性。

1961年,埃尔德什和塞凯赖什证明

1998年,一连三篇关于对的上界的文章被发表,其中最好的结果是由Tóth和Valtr找到的:

2005年,他们进一步将此上界降低了1:

2016年,Andrew Suk证明了:

参考

  • 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.

注解

  1. ^ 证明:若这五点的凸包是四边形或五边形,则结果易见。若否,则凸包是三角形,其中两点在三角形内。连接这两点的直线,与三角形其中两边相交,则这两点与三角形第三边的两点组成凸四边形。
  2. ^ Erdős & Szekeres (1961)
  3. ^ Suk, Andrew, On the Erdős–Szekeres convex polygon problem, 2016, arXiv:1604.08657

外部链接


本页面最后更新于2021-06-15 01:03,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器