跳至內容

種樹問題

維基百科,自由的百科全書
安排的九點(相關的冠毛配置)形成3點線。

離散幾何中,原始的果園種植問題要求的是在一個平面中過定點的3點線的可達到的最大數量。它也被稱為植樹造林問題,或只簡稱為果園問題。也可以是研究有多少k點線可以存在。Hallard T.克羅夫特和埃爾德什·帕爾證明了tk > c n2 / k3n是點的數量並且tkk點線的數量。[1]

他們的構造物包含了一些m-點線,其中m>k。你也可以問,如果這些是不允許的問題。

整數序列

定義t3果園(n)為過n定點可達到的3點線的最大數量。

在1974年,對於任意的正整數點nt3果園(n)被證明是(1/6)n2 − O(n)。

第一個t3果園(n)的數值在右表中(OEIS數列A003035).

n 4 5 6 7 8 9 10 11 12 13 14
t3果園(n) 1 2 4 6 7 10 12 16 19 22 26

上極限和下極限

由於沒有兩個直線可以共同經過兩個不同點,一個平凡的3點線的數量上限由以下n點的情況確定

事實是數的2點線至少是6n/13 (Csima & Sawyer 1993),該上限可以降低到

t3果園(n)的下限由通過定點的許多的3點線的構造給出。最早的二次方程式下限-(1/8)n2西爾維斯特給出,他在三次曲線y = x3放了n個點。這在1974年由 Burr, Grünbaum, and Sloane (1974採用一個魏爾斯特拉斯橢圓函數基礎上的結構改善至[(1/6)n2 − (1/2)n] + 1。一個Füredi & Palásti (1984)建立的圓內螺線基本的構造取得了相同的下限。

在2013年九月, Ben Green和陶哲軒發表的一篇論文中,他們證明了所有的點集必然的大小,n > n0,至多有([n(n - 3)/6]  + 1) = [(1/6)n2 − (1/2)n + 1] 3點線,其中相應的下限由Burr, Grünbaum和Sloane確立。[2] 這有一個比直接從他們的緊的下限得出的2點線的數n/2要略勝一籌的極限:[n(n − 2)/6],分別由Gabriel Andrew Dirac和Theodore Motzkinproved 在相同的論文中和解決一個1951問題以獨立地身份證明。

註釋

  1. ^ The Handbook of Combinatorics, edited by László_Lovász, {葛立恆, et al, in the chapter titled Extremal Problems in Combinatorial Geometry by Paul_Erdős and George_B._Purdy英語George_B._Purdy.
  2. ^ Green & Tao (2013)

參考文獻

外部連結

  1. ^ Green, Ben; Tao, Terence, On sets defining few ordinary lines, Discrete and Computational Geometry, 2013, 50 (2): 409–468, doi:10.1007/s00454-013-9518-9