Problema de no tener tres en la fila

Problema de geometría en puntos de la cuadrícula

Un conjunto de 20 puntos en una cuadrícula de 10 × 10, sin tres puntos en una línea.

El problema de no encontrar tres puntos en la línea en geometría discreta plantea la pregunta de cuántos puntos se pueden colocar en la cuadrícula de modo que no haya tres puntos en la misma línea. El problema se refiere a líneas de todas las pendientes , no solo a aquellas alineadas con la cuadrícula. Fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo llaman "una de las cuestiones geométricas más antiguas y estudiadas sobre los puntos de la red". ^[1] ${\displaystyle n\times n}$

Se pueden colocar como máximo 100 puntos, ya que los puntos de una cuadrícula incluirían una fila de tres o más puntos, según el principio del palomar . Aunque el problema se puede resolver con puntos para cada hasta , se conjetura que se pueden colocar menos de 100 puntos en cuadrículas de gran tamaño. Los métodos conocidos pueden colocar linealmente muchos puntos en cuadrículas de tamaño arbitrario, pero los mejores de estos métodos colocan ligeramente menos de 100 puntos, no 100 . ${\displaystyle 2n}$ ${\displaystyle 2n+1}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle 46}$ ${\displaystyle 2n}$ ${\displaystyle 1.5n}$ ${\displaystyle 2n}$

También se han estudiado varios problemas relacionados con la búsqueda de puntos sin tres en la línea, entre otros conjuntos de puntos que no sean cuadrículas. Aunque se originó en las matemáticas recreativas , el problema de los tres en la línea tiene aplicaciones en el dibujo de gráficos y en el problema del triángulo de Heilbronn .

Pequeñas instancias

Solución al rompecabezas de Dudeney de colocar 16 peones en un tablero de ajedrez de manera que no haya tres peones en la misma línea, con dos peones en las casillas d4 y e5.

El problema fue planteado por primera vez por Henry Dudeney en 1900, como un rompecabezas de matemáticas recreativas, expresado en términos de colocar los 16 peones de un tablero de ajedrez sobre el tablero de modo que no haya tres en línea. ^[2] Este es exactamente el problema de no haber tres en línea, para el caso . ^[3] ${\displaystyle n=8}$ En una versión posterior del rompecabezas, Dudeney modificó el problema, haciendo que su solución fuera única, al pedir una solución en la que dos de los peones estuvieran en las casillas d4 y e5 , atacándose entre sí en el centro del tablero. ^[4]

Muchos autores han publicado soluciones a este problema para valores pequeños de , ^[5] ${\displaystyle n}$ y en 1998 se sabía que se podían colocar puntos en una cuadrícula sin tres en una línea para todos hasta 46, y algunos valores mayores. ^[6] La cantidad de soluciones con puntos para valores pequeños de , a partir de , es ${\displaystyle 2n}$ ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n=2}$

1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, ... (secuencia A000755 en la OEIS ).

Los números de clases de equivalencia de soluciones con puntos bajo reflexiones y rotaciones son ${\displaystyle 2n}$

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (secuencia A000769 en la OEIS ). ^[3]

Límites superior e inferior

No se conoce el número exacto de puntos que se pueden colocar en función de . ${\displaystyle n}$ Sin embargo, tanto los límites probados como los conjeturados limitan este número dentro de un rango proporcional a . ${\displaystyle n}$

Métodos generales de colocación

Colocación subóptima de puntos en la cuadrícula, utilizando el método de Erdős. El primo más grande menor que el tamaño de la cuadrícula es ; la solución coloca los puntos en coordenadas mod para . Por ejemplo, se incluye porque ( mod ). ${\displaystyle 11}$ ${\displaystyle 12\times 12}$ ${\displaystyle p}$ ${\displaystyle p=11}$ ${\displaystyle (i,i^{2}}$ ${\displaystyle p)}$ ${\displaystyle i=0,1,\dots p-1}$ ${\displaystyle (4,5)}$ ${\displaystyle 4^{2}=16\cong 5}$ ${\displaystyle }$ ${\displaystyle 11}$

Una solución de Paul Erdős , publicada por Roth (1951), se basa en la observación de que cuando es un número primo , el conjunto de puntos de la cuadrícula mod , para , no contiene tres puntos colineales. Cuando no es primo, se puede realizar esta construcción para una cuadrícula contenida en la cuadrícula, donde es el primo más grande que es como máximo . Debido a que la brecha entre primos consecutivos es mucho menor que los primos mismos, siempre estará cerca de , por lo que este método se puede utilizar para colocar puntos en la cuadrícula sin tres puntos colineales. ^[7] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (i,i^{2}}$ ${\displaystyle n)}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle n}$ ${\displaystyle p\times p}$ ${\displaystyle n\times n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n-o(n)}$ ${\displaystyle n\times n}$

La cota de Erdős se ha mejorado posteriormente: Hall et al. (1975) muestran que, cuando es primo, se puede obtener una solución con puntos, colocando puntos en múltiples copias de la hipérbola (mod ), donde puede elegirse arbitrariamente siempre que sea distinto de cero mod . Nuevamente, para arbitrario se puede realizar esta construcción para un primo cercano para obtener una solución con puntos. ^[8] ${\displaystyle n/2}$ ${\displaystyle 3(n-2)/2}$ ${\displaystyle xy=k}$ ${\displaystyle n/2}$ ${\displaystyle k}$ ${\displaystyle n/2}$ ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle {\tfrac {3}{2}}n-o(n)}$

Límite superior

Como máximo, se pueden colocar puntos en una cuadrícula de cualquier tamaño . Porque, si se colocan más puntos, entonces, por el principio del palomar, unos tres de ellos se encontrarían todos en la misma línea horizontal de la cuadrícula. Para , se sabe que este límite trivial es estricto. ^[3] ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n\leq 46}$

Límites conjeturados

Aunque se pueden colocar exactamente puntos en cuadrículas pequeñas, Guy y Kelly (1968) conjeturaron que para cuadrículas grandes, existe un límite superior significativamente menor en la cantidad de puntos que se pueden colocar. Más precisamente, conjeturaron que la cantidad de puntos que se pueden colocar es como máximo una cantidad sublineal mayor que , con ^[9] Después de que se descubrió un error en el razonamiento heurístico que condujo a esta conjetura, Guy corrigió el error y formuló la conjetura más sólida de que no se puede hacer más que sublinealmente mejor que con ^[10] ${\displaystyle 2n}$ ${\displaystyle cn}$ $${\displaystyle c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1.874.}$$ ${\displaystyle cn}$ $${\displaystyle c={\frac {\pi }{\sqrt {3}}}\approx 1.814.}$$

Aplicaciones

Las soluciones al problema de no-tres-en-la-línea se pueden utilizar para evitar ciertos tipos de degeneraciones en el dibujo de grafos . El problema al que se aplican implica colocar los vértices de un grafo dado en coordenadas enteras en el plano y dibujar los bordes del grafo como segmentos de línea recta . Para ciertos grafos, como el grafo de utilidad , los cruces entre pares de bordes son inevitables, pero uno debe evitar colocaciones que hagan que un vértice se encuentre en un borde a través de otros dos vértices. Cuando los vértices se colocan sin tres en la línea, este tipo de colocación problemática no puede ocurrir, porque toda la línea a través de dos vértices cualesquiera, y no solo el segmento de línea, está libre de otros vértices. ^[11] El hecho de que el problema de no-tres-en-línea tenga una solución con muchos puntos linealmente puede traducirse en términos de dibujo de grafos en el sentido de que cada grafo, incluso un grafo completo , puede dibujarse sin incidencias no deseadas de aristas de vértice utilizando una cuadrícula cuya área es cuadrática en el número de vértices, y que para grafos completos no es posible tal dibujo con un área menor que cuadrática. Los grafos completos también requieren un número lineal de colores en cualquier coloración de grafos , pero otros grafos que pueden colorearse con menos colores también pueden dibujarse en cuadrículas más pequeñas: si un grafo tiene vértices y una coloración de grafos con colores, puede dibujarse en una cuadrícula con un área proporcional a . El dibujo de no-tres-en-línea de un grafo completo es un caso especial de este resultado con . ^[12] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle nk}$ ${\displaystyle k=n}$

El problema de no-tres-en-línea también tiene aplicaciones a otro problema en geometría discreta, el problema del triángulo de Heilbronn . En este problema, uno debe colocar puntos, en cualquier lugar en un cuadrado unitario, no restringido a una cuadrícula. El objetivo de la colocación es evitar triángulos de área pequeña, y más específicamente maximizar el área del triángulo más pequeño formado por tres de los puntos. Por ejemplo, una colocación con tres puntos en línea sería muy mala según este criterio, porque estos tres puntos formarían un triángulo degenerado con área cero. Por otro lado, si los puntos se pueden colocar en una cuadrícula de longitud de lado dentro del cuadrado unitario, sin tres en una línea, entonces por el teorema de Pick cada triángulo tendría área al menos , la mitad de un cuadrado de cuadrícula. Por lo tanto, resolver una instancia del problema de no-tres-en-línea y luego reducir la escala de la cuadrícula entera para que encaje dentro de un cuadrado unitario produce soluciones al problema del triángulo de Heilbronn donde el triángulo más pequeño tiene área . Esta aplicación fue la motivación para que Paul Erdős encontrara su solución para el problema del triángulo de Heilbronn. ^[13] Siguió siendo el mejor límite inferior del área conocido para el problema del triángulo de Heilbronn desde 1951 hasta 1982, cuando se mejoró con un factor logarítmico utilizando una construcción que no se basaba en el problema del triángulo de Heilbronn. ^[14] ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon ^{2}/2}$ ${\displaystyle \Omega (1/n^{2})}$

Generalizaciones y variaciones

Subconjuntos de posición general

En geometría computacional , se dice que los conjuntos finitos de puntos sin ningún tres en la línea están en posición general . En esta terminología, el problema de no-tres-en-la-línea busca el subconjunto más grande de una cuadrícula que esté en posición general, pero los investigadores también han considerado el problema de encontrar el subconjunto de posición general más grande de otros conjuntos de puntos que no sean de la cuadrícula. Es NP-difícil encontrar este subconjunto, para ciertos conjuntos de entrada, y difícil aproximar su tamaño dentro de un factor constante; este resultado de dificultad de aproximación se resume diciendo que el problema es APX-difícil . Si el subconjunto más grande tiene tamaño , ${\displaystyle k}$ se puede obtener una solución con la razón de aproximación no constante mediante un algoritmo voraz que simplemente elige los puntos uno a la vez hasta que todos los puntos restantes se encuentren en líneas a través de pares de puntos elegidos. ^[15] ${\displaystyle O({\sqrt {k}})}$

Se puede obtener una comprensión más precisa del tiempo de ejecución de los algoritmos para encontrar la solución óptima exacta utilizando la complejidad parametrizada , en la que los algoritmos se analizan no solo en términos del tamaño de entrada, sino en términos de otros parámetros de la entrada. En este caso, para las entradas cuyo subconjunto de posición general más grande tiene un tamaño , ${\displaystyle k}$ se puede encontrar en una cantidad de tiempo que es una función exponencial de multiplicada por un polinomio en el tamaño de entrada , con el exponente del polinomio que no depende de . Los problemas con este tipo de límite de tiempo se denominan manejables con parámetros fijos . ^[16] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Para conjuntos de puntos que tienen como máximo puntos por línea, con , existen subconjuntos de posición general de tamaño casi proporcional a . El ejemplo de la cuadrícula muestra que este límite no se puede mejorar significativamente. ^[17] La ​​prueba de existencia de estos grandes subconjuntos de posición general se puede convertir en un algoritmo de tiempo polinomial para encontrar un subconjunto de posición general de , de tamaño que coincida con el límite de existencia, utilizando una técnica algorítmica conocida como compresión de entropía . ^[15] ${\displaystyle S}$ ${\textstyle \ell }$ ${\textstyle \ell =O({\sqrt {|S|}})}$ ${\textstyle \ell =O({\sqrt {|S|}})}$ ${\displaystyle S}$

Colocación codiciosa

Repitiendo una sugerencia de Adena, Holton y Kelly (1974), Martin Gardner pidió el subconjunto más pequeño de una cuadrícula que no se puede extender: no tiene tres puntos en una línea, pero cada superconjunto propio tiene tres en una línea. Equivalentemente, este es el conjunto más pequeño que podría producirse mediante un algoritmo voraz que intenta resolver el problema de no tener tres puntos en una línea colocando los puntos uno a la vez hasta que se queda atascado. ^[3] Si solo se consideran líneas paralelas al eje y diagonales, entonces cada conjunto de este tipo tiene al menos puntos. ^[18] Sin embargo, se sabe menos sobre la versión del problema donde se consideran todas las líneas: cada colocación voraz incluye al menos puntos antes de quedarse atascada, pero no se conoce nada mejor que el límite superior trivial . ^[19] ${\displaystyle n\times n}$ ${\displaystyle n-1}$ ${\displaystyle \Omega (n^{2/3})}$ ${\displaystyle 2n}$

Dimensiones superiores

Pór y Wood (2007) consideraron conjuntos de puntos no colineales en la cuadrícula tridimensional. Demostraron que el número máximo de puntos en la cuadrícula sin tres puntos colineales es . De manera similar a la construcción 2D de Erdős, esto se puede lograr utilizando puntos mod , donde es un primo congruente con 3 mod 4 . ^[20] Así como el problema original de no tres en línea se puede utilizar para el dibujo de gráficos bidimensionales, se puede utilizar esta solución tridimensional para dibujar gráficos en la cuadrícula tridimensional. Aquí la condición de no colinealidad significa que un vértice no debe estar en un borde no adyacente, pero es normal trabajar con el requisito más estricto de que no se crucen dos bordes. ^[21] ${\displaystyle n\times n\times n}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle (x,y,x^{2}+y^{2}}$ ${\displaystyle p)}$ ${\displaystyle p}$

En dimensiones mucho más altas, los conjuntos de puntos de la cuadrícula sin tres en línea, obtenidos al elegir puntos cerca de una hiperesfera , se han utilizado para encontrar grandes conjuntos de Salem-Spencer , conjuntos de números enteros sin tres que forman una progresión aritmética. ^[22] Sin embargo, no funciona bien utilizar esta misma idea de elegir puntos cerca de un círculo en dos dimensiones: este método encuentra puntos que forman polígonos convexos, que satisfacen el requisito de no tener tres en línea, pero son demasiado pequeños. Los polígonos convexos más grandes con vértices en una cuadrícula solo tienen vértices. ^[23] El problema del conjunto de límites se refiere a un problema similar al problema de no tener tres en línea en espacios que son de alta dimensión y se basan como espacios vectoriales sobre cuerpos finitos en lugar de sobre números enteros. ^[24] ${\displaystyle n\times n}$ ${\displaystyle O(n^{2/3})}$

Otra generalización a dimensiones superiores consiste en encontrar tantos puntos como sea posible en una cuadrícula tridimensional de forma que no haya cuatro de ellos en el mismo plano. Esta secuencia comienza con 5, 8, 10, 13, 16, ... OEIS : A280537 para N = 2, 3, 4 , etc. ${\displaystyle N\times N\times N}$

Toro

Otra variación del problema implica convertir la cuadrícula en un toro discreto mediante el uso de condiciones de contorno periódicas en las que el lado izquierdo del toro está conectado al lado derecho y el lado superior está conectado al lado inferior. Esto tiene el efecto, en líneas inclinadas a través de la cuadrícula, de conectarlas en líneas más largas a través de más puntos y, por lo tanto, hacer más difícil seleccionar puntos con un máximo de dos de cada línea. Estas líneas extendidas también se pueden interpretar como líneas normales a través de una cuadrícula infinita en el plano euclidiano, tomadas módulo las dimensiones del toro. Para un toro basado en una cuadrícula, el número máximo de puntos que se pueden elegir sin tres en la línea es como máximo . ^[25] Cuando ambas dimensiones son iguales y primos, no es posible colocar exactamente un punto en cada fila y columna sin formar un número lineal de triples colineales. ^[26] También se han estudiado versiones del problema con toros de dimensiones superiores. ^[27] ${\displaystyle m\times n}$ ${\displaystyle 2\gcd(m,n)}$

Véase también

• Rompecabezas de ocho reinas , sobre la colocación de puntos en una cuadrícula sin dos en la misma fila, columna o diagonal.

Notas

1. Latón, Moser y Pach 2005.
2. The Weekly Dispatch , 29 de abril y 13 de mayo de 1900, citado por Knuth 2008.
3. 1976.
4. Dudeney1917.
5. Craggs y Hughes-Jones 1976; Klove 1978, 1979; Anderson 1979; Harborth, Oertel y Prellberg 1989; Flammenkamp 1992, 1998.
6. Flammenkamp 1992, 1998.
7. Erdős no publicó esta observación; aparece en Roth 1951.
8. Hall y otros 1975.
9. Guy y Kelly 1968.
10. Según informó Pegg 2005. Pegg atribuyó el descubrimiento de este error a Gabor Ellmann.
11. Latón y otros 2007.
12. Madera 2005.
13. Roth 1951.
14. Komlós, Pintz y Szemerédi 1982.
15. Eppstein 2018.
16. Froese y col. 2017; Eppstein 2018
17. Payne y Wood 2013.
18. Cooper y otros. 2014.
19. Aichholzer, Eppstein y Hainzl (2023).
20. Por y Wood 2007.
21. Pach, Thiele y Tóth 1998; Dujmović, Morin y Wood 2005; Di Giacomo, Liotta y Meijer 2005
22. Elkin 2011.
23. Jarnik 1926.
24. Clarreich 2016.
25. Misiak y otros. 2016.
26. Cooper y Solymosi 2005.
27. Ku y Wong 2018.

Referencias

• Adena, Michael A.; Holton, Derek A.; Kelly, Patrick A. (1974). "Algunas reflexiones sobre el problema de no-tres-en-línea". En Holton, Derek A. (ed.). Combinatorial Mathematics: Proceedings of the Second Australian Conference (Universidad de Melbourne, 1973) . Lecture Notes in Mathematics. Vol. 403. págs. 6–17. doi :10.1007/BFb0057371. MR  0349396.
• Aichholzer, Oswin; Eppstein, David ; Hainzl, Eva-Maria (enero de 2023). "Conjuntos geométricos dominantes: una versión mínima del problema de no tres en línea". Geometría computacional . 108 . Elsevier: 101913. arXiv : 2203.13170 . doi : 10.1016/j.comgeo.2022.101913 . S2CID  249687906.
• Anderson, David Brent (1979). "Actualización sobre el problema de no-tres-en-línea". Journal of Combinatorial Theory . Serie A. 27 (3): 365–366. doi : 10.1016/0097-3165(79)90025-6 . MR  0555806.
• Brass, Peter; Cenek, Eowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna ; Mitchell, Joseph SB (2007). "Sobre incrustaciones simultáneas de grafos planos". Geometría Computacional . 36 (2): 117–130. doi : 10.1016/j.comgeo.2006.05.006 . MR  2278011.
• Brass, Peter; Moser, William; Pach, János (2005). "Sección 10.1: Empaquetamiento de puntos reticulares en subespacios". Problemas de investigación en geometría discreta . Springer, Nueva York. pp. 417–421. ISBN 978-0-387-29929-7.Sr. 2163782  .
• Cooper, Alec S.; Pikhurko, Oleg; Schmitt, John R.; Warrington, Gregory S. (2014). "El problema del número 3 en una línea mínima de Martin Gardner". American Mathematical Monthly . 121 (3): 213–221. arXiv : 1206.5350 . doi :10.4169/amer.math.monthly.121.03.213. JSTOR  10.4169/amer.math.monthly.121.03.213. S2CID  887220.
• Cooper, Joshua N.; Solymosi, József (2005). "Puntos colineales en permutaciones" (PDF) . Anales de Combinatoria . 9 (2): 169–175. arXiv : math/0408396 . doi :10.1007/s00026-005-0248-4. MR  2153735. S2CID  11035679.
• Craggs, D.; Hughes-Jones, R. (1976). "Sobre el problema de no-tres-en-línea". Journal of Combinatorial Theory . Serie A. 20 (3): 363–364. doi : 10.1016/0097-3165(76)90030-3 . MR  0406804.
• Dudeney, Henry (1917). "317. Un rompecabezas con peones". Diversiones en matemáticas . Edimburgo: Nelson. pág. 94.Solución, pág. 222. Publicado originalmente en el London Tribune , 7 de noviembre de 1906.
• Di Giacomo, Emilio; Liotta, Giuseppe; Meijer, Henk (2005). "Cálculo de dibujos de cuadrículas 3D en línea recta de grafos en volumen lineal". Geometría computacional: teoría y aplicaciones . 32 (1): 26–58. doi :10.1016/j.comgeo.2004.11.003.
• Dujmović, Vida ; Morin, Pat ; Wood, David R. (2005). "Diseño de gráficos con ancho de árbol acotado". Revista SIAM de Computación . 34 (3): 553–579. arXiv : cs/0406024 . doi :10.1137/S0097539702416141. S2CID  3264071.
• Elkin, Michael (2011). "Una construcción mejorada de conjuntos libres de progresión". Revista israelí de matemáticas . 184 : 93–128. arXiv : 0801.4310 . doi : 10.1007/s11856-011-0061-1 . MR  2823971.
• Eppstein, David (2018). "Capítulo 9: Posición general". Configuraciones prohibidas en geometría discreta . Cambridge University Press. págs. 72–86.
• Flammenkamp, ​​Achim (1992). "Progreso en el problema de no-tres-en-línea". Journal of Combinatorial Theory . Serie A. 60 (2): 305–311. doi : 10.1016/0097-3165(92)90012-J .
• Flammenkamp, ​​Achim (1998). "Progreso en el problema de no-tres-en-línea, II". Journal of Combinatorial Theory . Serie A. 81 (1): 108–113. doi : 10.1006/jcta.1997.2829 .
• Froese, Vincent; Kanj, Iyad; Nichterlein, André; Niedermeier, Rolf (2017). "Encontrar puntos en posición general". Revista Internacional de Geometría Computacional y Aplicaciones . 27 (4): 277–296. arXiv : 1508.01097 . doi :10.1142/S021819591750008X. MR  3766097. S2CID  47260245.
• Gardner, Martin (octubre de 1976). "Problemas combinatorios, algunos antiguos, otros nuevos y todos abordados recientemente por ordenador". Juegos matemáticos. Scientific American . Vol. 235, núm. 4. págs. 131–137. JSTOR  24950467.
• Guy, RK ; Kelly, PA (1968). "El problema de no-tres-en-línea". Canadian Mathematical Bulletin . 11 (4): 527–531. doi : 10.4153/CMB-1968-062-3 . MR  0238765.
• Hall, RR; Jackson, TH; Sudbery, A.; Wild, K. (1975). "Algunos avances en el problema de no-tres-en-línea". Journal of Combinatorial Theory . Serie A. 18 (3): 336–341. doi : 10.1016/0097-3165(75)90043-6 .
• Harborth, Heiko ; Oertel, Philipp; Prellberg, Thomas (1989). "No-three-in-line for seventeen and nineteen". Actas de la reunión de Oberwolfach “Kombinatorik” (1986). Matemáticas discretas . 73 (1–2): 89–90. doi : 10.1016/0012-365X(88)90135-5 . MR  0974815.
• Jarník, Vojtěch (1926). "Über die Gitterpunkte auf konvexen Kurven" [Sobre los puntos de la cuadrícula en curvas convexas]. Mathematische Zeitschrift (en alemán). 24 (1): 500–518. doi :10.1007/BF01216795. SEÑOR  1544776. S2CID  117747514.
• Klarreich, Erica (31 de mayo de 2016). "La prueba del juego de conjuntos simple sorprende a los matemáticos". Quanta .
• Kløve, Torleiv (1978). "Sobre el problema de no-tres-en-línea. II". Journal of Combinatorial Theory . Serie A. 24 (1): 126–127. doi : 10.1016/0097-3165(78)90053-5 . MR  0462998.
• Kløve, Torleiv (1979). "Sobre el problema de no-tres-en-línea. III". Revista de Teoría Combinatoria . Serie A. 26 (1): 82–83. doi :10.1016/0097-3165(79)90055-4. MR  0525088.
• Komlós, J .; Pintz, J .; Szemerédi, E. (1982). "Un límite inferior para el problema de Heilbronn". Revista de la Sociedad Matemática de Londres . 25 (1): 13–24. doi :10.1112/jlms/s2-25.1.13. SEÑOR  0645860.
• Knuth, Donald E. (2008). "Respuesta al ejercicio 242". El arte de la programación informática, fascículo 1b: borrador de la sección 7.1.4: Diagramas de decisión binaria . pág. 130.
• Ku, Cheng Yeaw; Wong, Kok Bin (2018). "Sobre el problema de no tres en línea en un toro m -dimensional". Graphs and Combinatorics . 34 (2): 355–364. doi :10.1007/s00373-018-1878-8. MR  3774457. S2CID  3935268.
• Misiak, Aleksander; Stępień, Zofia; Szymaszkiewicz, Alicja; Szymaszkiewicz, Lucjan; Zwierzchowski, Maciej (2016). "Una nota sobre el problema del no tres en línea en un toroide". Matemáticas Discretas . 339 (1): 217–221. arXiv : 1406.6713 . doi :10.1016/j.disc.2015.08.006. SEÑOR  3404483. S2CID  40210322.
• Pach, János ; Thiele, Torsten; Tóth, Géza (1998). "Dibujos de grafos en cuadrícula tridimensional". Graph Drawing, 5th Int. Symp., GD '97 . Lecture Notes in Computer Science. Vol. 1353. Springer-Verlag. págs. 47–51. doi : 10.1007/3-540-63938-1_49 .
• Payne, Michael S.; Wood, David R. (2013). "Sobre el problema general de selección de subconjuntos de posiciones". Revista SIAM de Matemáticas Discretas . 27 (4): 1727–1733. arXiv : 1208.5289 . doi :10.1137/120897493. MR  3111653. S2CID  7164626.
• Pegg, Ed Jr. (11 de abril de 2005). «Chessboard Tasks». Juegos de matemáticas . Asociación Matemática de Estados Unidos . Consultado el 25 de junio de 2012 .
• Pór, Attila; Wood, David R. (2007). "No-tres-en-línea-en-3D". Algorithmica . 47 (4): 481. doi :10.1007/s00453-006-0158-9. S2CID  209841346.
• Roth, KF (1951). "Sobre un problema de Heilbronn". Revista de la Sociedad Matemática de Londres . 26 (3): 198–204. doi :10.1112/jlms/s1-26.3.198.
• Wood, David R. (2005). "Dibujos en cuadrícula de grafos coloreables". Geometría computacional: teoría y aplicaciones . 30 (1): 25–28. doi : 10.1016/j.comgeo.2004.06.001 .

Enlaces externos

• Flammenkamp, ​​Achim. "El problema de no tener tres en la fila".
• Weisstein, Eric W. "No hay problema de tres en una línea". MathWorld .