A geometric Ramsey problem

Question

The following problem seems like one to which the answer could well be known: if so, I'd be interested to have a reference.

How large does n have to be such that among any n points in the plane you can find either m points that are collinear or m points such that no three are collinear? The fact that n is finite follows from Ramsey's theorem: colour triples of points according to whether they are collinear.

However, as with many geometric colourings, far better bounds hold than what one can obtain from the abstract Ramsey theorem. Here are what seem to me to be the trivial bounds. In one direction, an m-by-m grid of points does not contain more than m in a line, but if you choose 2m+1 of the points then you must have three that are collinear. So you need at least $cm^2$ points. (It's not quite obvious that you can choose linearly many points in this grid with no three in a line, but an old idea of Erdős does the trick: assume that m is prime and choose all points (x,y) such that $y\equiv x^2$ mod m. It is not hard to check that this set does not contain three points that are in a line even in the mod-m sense, so certainly not in the integer sense. If m isn't prime, then discard a few points until it is.)

In the other direction, you can just greedily pick points such that no three are collinear. If you reach r points and then cannot extend your set, then all subsequent points lie in one of the $\binom r2$ lines defined by the points so far. Therefore, there must be $cn/r^2$ points in a line, by the pigeonhole principle. It follows that it is enough if $n=cm^3$.

My question is, is one of these two bounds known to be correct (up to $n^{o(1)}$), and if so which? It feels quite close to known incidence results: another possibility is that a simple adaptation of a known argument would answer the question. The one thing that suggests that it might be hard is the fact that it takes a slight effort to find that set of points in the grid with no three in a line.

Answer 1

A type of generalization of the Erdős–Szekeres Theorem is that every set of at least $n= (m-3) \binom{k-1}{2} +k$ points in the plane contains either $m$ collinear points or $k$ points in general position. Specializing this to $k=m$ yields an expression in $O(m^3)$, matching your upper bound. Unfortunately I cannot access proofs at the moment, and so am uncertain if the bound is known to be tight. I have seen this result cited as in Peter Brass, "On point sets without $k$ collinear points," Discrete Geometry, 185-192, 2003; and in Zoltan Füredi, "Maximal independent subsets in Steiner systems and in planar sets," SIAM J. Discrete Math. 4(2), 196-199.

In any case, I think your question is a specialization of a generalization of the Erdős–Szekeres Theorem.

Answer 2

This question has been answered up to a logarithmic factor by Michael Payne and myself ["On the general position subset selection problem"]. We show that $n \leqslant c m^2 \log m$. The proof employs the Szemeredi-Trotter Theorem to bound the number of collinear triples in a point set. Then we apply known results about independent sets in 3-uniform hypergraphs to conclude the result.

I think the answer should be $cm^2$. That is, every set of at least $cm^2$ points contains $m$ collinear points or $m$ points with no three collinear (for some constant $c>0$).