![](/files/happy5.png)
General position subsets
![$ f(n) $](/files/tex/9579fe06c51fc31a993cd148e8bbc3cb07df464e.png)
![$ f(n) $](/files/tex/9579fe06c51fc31a993cd148e8bbc3cb07df464e.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
The grid contains no set of
collinear points and no subset of
points in general position, implying
.
To see that , consider a set
of points that contain no
collinear points, and contain no subset of
points in general position. Let
be a maximal subset of
in general position. Every point in
is on one of the
lines determined by
. Each such line contains at most
points in
. Thus
.
Payne and Wood [PW] improved this upper bound to . The proof is based on the Szemerédi-Trotter Theorem and Spencer's Lemma about independent sets in hypergraphs.
It is reasonable to think that the grid is the extremal example, and . This would be an elegant generalisation of a result by Erdős [R] who proved that the
grid contains a subset of
points in general position (the no-three-in-line problem).
Bibliography
*[G] Timothy Gowers, A geometric Ramsey problem.
[PW] Michael Payne, David R. Wood. On the general position subset selection problem, SIAM J. Discrete Math. 27.4:1727-1733, 2013.
[R] K. F. Roth, On a problem of Heilbronn, J. London Mathematical Society 26.3:198–204, 1951.
* indicates original appearance(s) of problem.