幸福結局問題(由保羅·艾狄胥命名,因為這個問題令喬治·塞凱賴什和愛絲特·克萊共諧連理)是問,在平面上,給定一般位置(即平面上任意三點不共線)上的多少點,才令其中必可以找到點能組成凸邊形?
此條目需要擴充。 (2013年2月14日) |
1935年,艾狄胥和塞凱賴什證明:給定任意正整數,存在正整數使得給定在平面上一般位置上的點,其中必可以找到點能組成凸邊形。
將表示為的最小可能值,已知
- :顯然易見
- :愛絲特·克萊證明;這就是最初的問題[1]
- :艾狄胥和塞凱賴什表示E. Makai證明了這點,但首個印刷出來的證明則在1970年出現在Kalbfleisch et al
- :由塞凱賴什和Lindsay Peters以機器證明所有可能性。
1961年,艾狄胥和塞凱賴什證明 [2]。
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.
註解
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.