Un problema geométrico de Ramsey

Question

El siguiente problema parece ser uno cuya respuesta bien podría conocerse: si es así, me interesaría tener una referencia.

¿Cómo de grande tiene que ser n para que entre n puntos cualesquiera del plano se encuentren o bien m puntos que sean colineales o bien m puntos tales que no haya tres colineales? El hecho de que n sea finito se deduce del teorema de Ramsey: colorea los triples de puntos según sean colineales o no.

Sin embargo, como ocurre con muchas coloraciones geométricas, existen límites mucho mejores que los que se pueden obtener a partir del teorema abstracto de Ramsey. He aquí lo que me parecen los límites triviales. En una dirección, una cuadrícula de puntos m por m no contiene más de m en una línea, pero si eliges 2m+1 de los puntos, entonces debes tener tres que sean colineales. Así que necesitas al menos $cm^2$ puntos. (No es del todo obvio que se puedan elegir linealmente muchos puntos en esta cuadrícula sin que haya tres en una línea, pero una vieja idea de Erdős sirve: supongamos que m es primo y elijamos todos los puntos (x,y) tales que $y\equiv x^2$ mod m. No es difícil comprobar que este conjunto no contiene tres puntos que estén en una recta, ni siquiera en el sentido mod-m, ni mucho menos en el sentido entero. Si m no es primo, entonces descarta algunos puntos hasta que lo sea).

En la otra dirección, se pueden elegir con avidez puntos de forma que no haya tres colineales. Si se alcanzan r puntos y no se puede ampliar el conjunto, todos los puntos siguientes se encuentran en uno de los siguientes puntos $\binom r2$ líneas definidas por los puntos hasta ahora. Por lo tanto, debe haber $cn/r^2$ puntos en una línea, por el principio de encasillamiento. De ello se deduce que basta con que $n=cm^3$ .

Mi pregunta es, ¿se sabe si uno de estos dos límites es correcto (hasta $n^{o(1)}$ ) y, en caso afirmativo, ¿cuáles? Se parece bastante a los resultados de incidencia conocidos: otra posibilidad es que una simple adaptación de un argumento conocido responda a la pregunta. Lo único que sugiere que podría ser difícil es el hecho de que cuesta un ligero esfuerzo encontrar ese conjunto de puntos de la cuadrícula sin tres en línea.

Answer 1

Un tipo de generalización de la Teorema de Erdős-Szekeres es que todo conjunto de al menos $n= (m-3) \binom{k-1}{2} +k$ puntos en el plano contiene $m$ puntos colineales o $k$ puntos en posición general. Especializando esto a $k=m$ produce una expresión en $O(m^3)$ que coincide con su límite superior. Por desgracia, no puedo acceder a las pruebas en este momento, y por lo tanto no estoy seguro de si el límite es conocido por ser apretado. He visto este resultado citado como en Peter Brass, " En conjuntos de puntos sin $k$ puntos colineales ," Geometría discreta , 185-192, 2003; y en Zoltan Füredi, " Subconjuntos máximos independientes en sistemas de Steiner y en conjuntos planares ," SIAM J. Discrete Math. 4(2), 196-199.

En cualquier caso, creo que tu pregunta es una especialización de una generalización de Teorema de Erdős-Szekeres.

Answer 2

Esta pregunta ha sido respondida hasta un factor logarítmico por Michael Payne y por mí mismo ["Sobre el problema general de selección de subconjuntos de posiciones"] . Demostramos que $n \leqslant c m^2 \log m$ . La prueba emplea el Teorema de Szemeredi-Trotter para acotar el número de triples colineales en un conjunto de puntos. A continuación, aplicamos resultados conocidos sobre conjuntos independientes en hipergrafos 3-uniformes para concluir el resultado.

Creo que la respuesta debería ser $cm^2$ . Es decir, todo conjunto de al menos $cm^2$ puntos contiene $m$ puntos colineales o $m$ puntos sin tres colineales (para alguna constante $c>0$ ).