Problema de plantación de huertos

Geometría; ¿cuántas líneas de 3 puntos pueden formar n puntos?

Una disposición de nueve puntos (relacionados con la configuración de Pappus ) que forman 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 ) pide 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 k puntos puede haber. Hallard T. Croft y Paul Erdős demostraron donde n es el número de puntos y t _k es el número de líneas de k puntos. ^[1] Su construcción contiene algunas líneas de m puntos, donde m > k . También se puede preguntar si estas no están permitidas. $${\displaystyle t_{k}>{\frac {cn^{2}}{k^{3}}},}$$

Secuencia de números enteros

Definir ⁠ ⁠ ${\displaystyle t_{3}^{\text{orchard}}(n)}$ 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, ⁠ ⁠ ${\displaystyle t_{3}^{\text{orchard}}(n)}$ se demostró que era en 1974. ${\displaystyle {\tfrac {1}{6}}n^{2}-O(n)}$

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

Límites superior e inferior

Dado que no pueden compartir dos líneas dos puntos distintos, un límite superior trivial para el número de líneas de 3 puntos determinado por n puntos es Usando el hecho de que el número de líneas de 2 puntos es al menos ⁠ ⁠ (Csima y Sawyer 1993), este límite superior se puede reducir a $${\displaystyle \left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .}$$ ${\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 para ⁠ ⁠ ${\displaystyle t_{3}^{\text{orchard}}(n)}$ se dan mediante 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 . Una construcción elemental utilizando hipocicloides fue encontrada por Füredi y Palásti (1984) logrando el mismo límite inferior. ${\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 3 líneas de puntos que coinciden con el límite inferior establecido por Burr, Grünbaum y Sloane. ^{[2] Por lo tanto, para} n suficientemente grande , se conoce el valor exacto de ⁠ ⁠ . $${\displaystyle {\frac {n(n-3)}{6}}+1={\frac {1}{6}}n^{2}-{\frac {1}{2}}n+1}$$ ${\displaystyle t_{3}^{\text{orchard}}(n)}$

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

El problema de plantación de huertos también se ha considerado en campos finitos. En esta versión del problema, los n puntos se encuentran en un plano proyectivo definido en 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

• Brass, 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 un gran número de triángulos", Actas de la American Mathematical Society , 92 (4): 561–566, doi :10.2307/2045427, JSTOR  2045427.
• Green, Ben ; Tao, Terence (2013), "Sobre conjuntos que definen pocas líneas ordinarias", Geometría discreta y computacional , 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. , "El problema de la plantación de huertos", MathWorld