Problema de plantación de huertos

Geometría; ¿Cuántas rectas de 3 puntos se pueden formar n puntos?

Un arreglo de nueve puntos (relacionado con la configuración Pappus ) formando diez líneas de 3 puntos.

En geometría discreta , el problema original de plantación de huertos (o el problema de plantación de árboles ) solicita el número máximo de líneas de 3 puntos alcanzables mediante una configuración de un número específico de puntos en el plano . También hay investigaciones sobre cuántas líneas de puntos k puede haber. Hallard T. Croft y Paul Erdős demostraron

$${\displaystyle t_{k}>{\frac {cn^{2}}{k^{3}}},}$$

nt _kk puntos. ^[1]de mm > k

secuencia entera

Definir como el número máximo de líneas de 3 puntos alcanzables con una configuración de n puntos. Para un número arbitrario de n puntos, se demostró que era en 1974. ${\displaystyle t_{3}^{\text{orchard}}(n)}$ ${\displaystyle t_{3}^{\text{orchard}}(n)}$ ${\displaystyle {\tfrac {1}{6}}n^{2}-O(n)}$

Los primeros valores de se dan en la siguiente tabla (secuencia A003035 en OEIS ). ${\displaystyle t_{3}^{\text{orchard}}(n)}$

Límites superior e inferior

Dado que no hay dos líneas que puedan compartir dos puntos distintos, un límite superior trivial para el número de líneas de 3 puntos determinado por n puntos es

$${\displaystyle \left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .}$$

el número de líneas de 2 puntos ${\displaystyle {\tfrac {6n}{13}}}$

$${\displaystyle \left\lfloor {\frac {{\binom {n}{2}}-{\frac {6n}{13}}}{3}}\right\rfloor =\left\lfloor {\frac {n^{2}}{6}}-{\frac {25n}{78}}\right\rfloor .}$$

Los límites inferiores de están dados por construcciones para conjuntos de puntos con muchas líneas de 3 puntos. El primer límite inferior cuadrático de fue dado por Sylvester , quien colocó n puntos en la curva cúbica y = x ³ . Esto fue mejorado en 1974 por Burr , Grünbaum y Sloane  (1974), utilizando una construcción basada en las funciones elípticas de Weierstrass . Füredi y Palásti (1984) encontraron una construcción elemental que utiliza hipocicloides y logra el mismo límite inferior. ${\displaystyle t_{3}^{\text{orchard}}(n)}$ ${\displaystyle \approx {\tfrac {1}{8}}n^{2}}$ ${\displaystyle {\tfrac {1}{6}}n^{2}-{\tfrac {1}{2}}n+1}$

En septiembre de 2013, Ben Green y Terence Tao publicaron un artículo en el que demuestran que para todos los conjuntos de puntos de tamaño suficiente, n > n ₀ , hay como máximo

$${\displaystyle {\frac {n(n-3)}{6}}+1={\frac {1}{6}}n^{2}-{\frac {1}{2}}n+1}$$

^{[2] Por lo tanto, para} n ${\displaystyle t_{3}^{\text{orchard}}(n)}$

Esto es ligeramente mejor que el límite que se seguiría directamente de su estrecho límite inferior para el número de líneas de 2 puntos : demostrado en el mismo artículo y resolviendo un problema de 1951 planteado de forma independiente por Gabriel Andrew Dirac y Theodore Motzkin . ${\displaystyle {\tfrac {n}{2}}}$ ${\displaystyle {\tfrac {n(n-2)}{6}},}$

También se ha considerado el problema de la plantación de huertos en campos finitos. En esta versión del problema, los n puntos se encuentran en un plano proyectivo definido sobre un campo finito (Padmanabhan y Shukla 2020).

Notas

1. The Handbook of Combinatorics , editado por László Lovász , Ron Graham , et al, en el capítulo titulado Problemas extremos en geometría combinatoria por Paul Erdős y George B. Purdy .
2. Verde y Tao (2013)

Referencias

• Latón, P.; Moser, WOJ; Pach, J. (2005), Problemas de investigación en geometría discreta , Springer-Verlag, ISBN 0-387-23815-8.
• Rebaba, SA ; Grünbaum, B .; Sloane, NJA (1974), "El problema del huerto", Geometriae Dedicata , 2 (4): 397–424, doi :10.1007/BF00147569, S2CID  120906839.
• Csima, J.; Sawyer, E. (1993), "Existen 6 n /13 puntos ordinarios", Geometría discreta y computacional , 9 (2): 187–202, doi : 10.1007/BF02189318.
• Füredi, Z .; Palásti, I. (1984), "Disposiciones de líneas con una gran cantidad de triángulos", Actas de la Sociedad Matemática Estadounidense , 92 (4): 561–566, doi :10.2307/2045427, JSTOR  2045427.
• Verde, Ben ; Tao, Terence (2013), "Sobre conjuntos que definen algunas líneas ordinarias", Geometría computacional y discreta , 50 (2): 409–468, arXiv : 1208.4714 , doi :10.1007/s00454-013-9518-9, S2CID  15813230
• Padmanabhan, R.; Shukla, Alok (2020), "Huertos en curvas elípticas sobre campos finitos", Campos finitos y sus aplicaciones , 68 (2): 101756, arXiv : 2003.07172 , doi : 10.1016/j.ffa.2020.101756, S2CID  212725631

enlaces externos

• Weisstein, Eric W. , "Problema de plantación de huertos", MathWorld