Skip to main content
added 181 characters in body
Source Link
David Wood
  • 1.3k
  • 9
  • 12

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

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.

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

Source Link
David Wood
  • 1.3k
  • 9
  • 12

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.