En geometría discreta , el problema original de plantación de huertos solicita el número máximo de líneas de 3 puntos que se pueden alcanzar mediante una configuración de un número específico de puntos en el plano. También se le llama problema de plantación de árboles o simplemente problema de huerto. También hay investigaciones sobre cuántas líneas de puntos k puede haber. Hallard T. Croft y Paul Erdős demostraron t k > c n 2 / k 3 , donde n es el número de puntos y t k es el número de k líneas de puntos . [1] Su construcción contiene algunoslíneas de puntos m , donde m > k . También se puede preguntar si estos no están permitidos.
Secuencia entera
Defina t 3 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 puntos, se demostró que n , t 3 orchard ( n ) era (1/6) n 2 - O (n) en 1974.
Los primeros valores de t 3 orchard ( n ) se dan en la siguiente tabla (secuencia A003035 en la OEIS ).
norte | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|
t 3 huerto ( n ) | 1 | 2 | 4 | 6 | 7 | 10 | 12 | dieciséis | 19 | 22 | 26 |
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
Usando el hecho de que el número de líneas de 2 puntos es al menos 6 n / 13 ( Csima y Sawyer 1993 ), este límite superior puede reducirse a
Los límites inferiores para t 3 orchard ( n ) están dados por construcciones para conjuntos de puntos con muchas líneas de 3 puntos. El primer límite inferior cuadrático de ~ (1/8) n 2 fue dado por Sylvester , quien colocó n puntos en la curva cúbica y = x 3 . Esto fue mejorado a [(1/6) n 2 - (1/2) n ] + 1 en 1974 por Burr , Grünbaum y Sloane ( 1974 ), usando 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 con 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 0 , hay como máximo ([ n ( n - 3) / 6] + 1) = [ (1/6) n 2 - (1/2) n + 1] Líneas de 3 puntos que coinciden con el límite inferior establecido por Burr, Grünbaum y Sloane. [2] Esto es ligeramente mejor que el límite que seguiría directamente de su límite inferior ajustado 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 de 1951 planteado independientemente por Gabriel Andrew Dirac y Theodore Motzkin .
Notas
- ↑ The Handbook of Combinatorics , editado por László Lovász , Ron Graham , et al, en el capítulo titulado Extremal Problems in Combinatorial Geometry por Paul Erdős y George B. Purdy .
- ↑ Green 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.
- Burr, SA ; Grünbaum, B .; Sloane, NJA (1974), "The Orchard problem", Geometriae Dedicata , 2 (4): 397–424, doi : 10.1007 / BF00147569.
- 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), "Arreglos de líneas con un gran número de triángulos", Proceedings of the 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
enlaces externos
- Weisstein, Eric W. "Problema de plantación de huertos" . MathWorld .