Maximum sets of lattice points such that only a few points collinear

Consider all the integer points $\in [0,n]\times[0,n]$, I want to find the maximum subset $S$ of which such that there are at most $n^\varepsilon(0<\varepsilon<1)$ points in $S$ collinear.

So, does any one can answer what magnitude of the size of $S$ will be?(write as the function $f(\varepsilon)$ of $\varepsilon$)

• Neglecting constants (which are no doubt going to be difficult), I am thinking about $n^{1+\epsilon}$ (obvious upper bound + random construction). – Peter Dukes Aug 26 '14 at 12:05
• I wonder how much this problem is related to mathoverflow.net/questions/181649/… . – Janne Kokkala Sep 26 '14 at 12:33

Not an answer, but it might help to start with the problem of avoiding all sets of $3$ collinear points, on which there is a large literature, summarized in

Brass, Peter, William OJ Moser, and János Pach. Research problems in discrete geometry. Vol. 18. New York: Springer, 2005.

on p.417. Perhaps roughly $2n$ noncollinear points can be found in an $n \times n$ square (although as Ben Green points out, only $\frac{3}{2} n$ has been proven): • It is, in fact, a very unsolved problem to decide whether you can put $2n$ points in $[n] \times [n]$ with no three collinear, if $n$ is large. I suspect the answer is no, and that in fact one can only put $(c + o(1))n$ such points for some $c < 2$; possibly $c = 3/2$. There is a construction which achieves this. – Ben Green Aug 26 '14 at 11:17
• Thanks for the remark; perhaps your hunch is closer to the truth. The $3/2$-construction is from: R.R. Hall, T.H. Jackson, A. Sudbery, K. Wild: "Some advances in the no-three-in-line problem," J. Combinatorial Theory Ser. A 18 (1975) 336–341. – Joseph O'Rourke Aug 26 '14 at 11:45
• Maybe you also want to link the wikipedia article: en.wikipedia.org/wiki/No-three-in-line_problem – domotorp Aug 26 '14 at 19:42