Problema del huerto

En geometría discreta, el problema original del huerto consiste en determinar el número máximo de líneas de 3 puntos que se puede alcanzar mediante una configuración dada de puntos en el plano. También se le llama el problema de la plantación de árboles o simplemente el problema de la huerta.

Una matriz de nueve puntos (relacionada con la configuración de Pappus) forma un máximo de 10 líneas de 3 puntos.

También se han realizado investigaciones sobre cuántas líneas de k-puntos pueden formarse. Hallard T. Croft y Paul Erdős demostraron que:

t_k > c n² / k³

donde n es el número total 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 plantear el problema en el caso de que estas configuraciones de más de k puntos alineados no están permitidas.

Secuencia de enteros

Se define t₃^huerto (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 puntos n, se demostró en 1974 que t₃^huerto (n) es (1/6) n².

Los primeros valores de t₃^huerto (n) se dan en la siguiente tabla (sucesión A003035 en OEIS).

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

Límites superior e inferior

Puesto 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 .}$

Utilizando el hecho de que según el Teorema de Sylvester-Gallai para el número de líneas de 2 puntos es al menos 6n/13 ^[2], este límite superior se puede rebajar a:

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

(donde la notación ${\displaystyle \left\lfloor x\right\rfloor }$ indica la función suelo)

Los límites inferiores para t₃^huerto(n) están dados por construcciones para conjuntos de puntos con muchas líneas de 3 puntos. El primer límite cuadrático inferior de ~(1/8)n² fue dado por Sylvester, quien situó n puntos en la curva cúbica y = x³. Esto se mejoró a [(1/6)n² − (1/2)n] + 1 en 1974 por ^[3], usando una construcción basada en funciones elípticas de Weierstrass. Una construcción elemental usando hipocicloides fue hallada por Füredi y Palásti (1984), logrando el mismo límite inferior.

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 ([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] líneas de 3 puntos, lo que coincide con el límite inferior establecido por Burr, Grünbaum y Sloane.^[4] Esto es ligeramente mejor que lo que resultaría directamente de su límite inferior estricto de n/2 para el número de líneas de 2 puntos: [n(n − 2)/6], demostrado en el mismo documento y resolviendo un problema planteado independientemente por Gabriel Andrew Dirac y Theodore Motzkin en 1951.

Referencias

1. The Handbook of Combinatorics, edited by László Lovász, Ron Graham, et al, in the chapter titled Extremal Problems in Combinatorial Geometry by Paul Erdős and George B. Purdy.
2. Csima y Sawyer, 1993.
3. Burr, Grünbaum y Sloane, 1974.
4. Green y Tao (2013)

Bibliografía

• Brass, P.; Moser, W. O. J.; Pach, J. (2005), Research Problems in Discrete Geometry, Springer-Verlag, ISBN 0-387-23815-8..
• Burr, S. A.; Grünbaum, B.; Sloane, N. J. A. (1974), «The Orchard problem», Geometriae Dedicata 2 (4): 397-424, doi:10.1007/BF00147569..
• Csima, J.; Sawyer, E. (1993), «There exist 6n/13 ordinary points», Discrete and Computational Geometry 9: 187-202, doi:10.1007/BF02189318..
• Füredi, Z.; Palásti, I. (1984), «Arrangements of lines with a large number of triangles», Proceedings of the American Mathematical Society 92 (4): 561-566, JSTOR 2045427, doi:10.2307/2045427..
• Green, Ben; Tao, Terence (2013), «On sets defining few ordinary lines», Discrete and Computational Geometry 50 (2): 409-468, doi:10.1007/s00454-013-9518-9.

Enlaces externos

• Weisstein, Eric W. «Orchard-Planting Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.

• Datos: Q7100169