MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## A geometric Ramsey problem

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.

-
 A similar looking question: Is there a number N(m) so that in any N points in the plane there are m that can see each other or m that are collinear? It's hard because "seeing each other" is not a property of the subset only. A point from the original set can block the visibility of two points from the subset. There is nice expository paper about this problem by Por and Wood who came up with this question. – Alfredo Hubard Nov 4 2011 at 22:21

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.

-
Thanks for those references. – gowers Jan 2 2011 at 18:34
I hope everyone understands (as Timothy does) that I have not answered his question: rather I have placed it in an historical context dating back to the 1935 Erdős–Szekeres paper, "A combinatorial problem in geometry." I still do not see how to adjudicate between Timothy's $m^2$ and $m^3$ bounds. – Joseph O'Rourke Jan 2 2011 at 22:22

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$).

-