跳转到内容

种树问题

维基百科,自由的百科全书
安排的九点(相关的冠毛配置)形成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