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

  • 2
    $\begingroup$ Neglecting constants (which are no doubt going to be difficult), I am thinking about $n^{1+\epsilon}$ (obvious upper bound + random construction). $\endgroup$ – Peter Dukes Aug 26 '14 at 12:05
  • $\begingroup$ I wonder how much this problem is related to mathoverflow.net/questions/181649/… . $\endgroup$ – 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):


| cite | improve this answer | |
  • 5
    $\begingroup$ 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. $\endgroup$ – Ben Green Aug 26 '14 at 11:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Aug 26 '14 at 11:45
  • 2
    $\begingroup$ Maybe you also want to link the wikipedia article: en.wikipedia.org/wiki/No-three-in-line_problem $\endgroup$ – domotorp Aug 26 '14 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.