Big Line or Big Clique in Planar Point Sets
Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .
The conjecture is trivial for .
Kára et al. [KPW] proved the conjecture for and all .
Addario-Berry et al. [AFKCW] proved the conjecture for and .
Abel et al. [ABBCDHKLPW] proved the conjecture for and all .
The conjecture is open for or .
Note that it is easily proved that for all , every set of at least points in the plane contains collinear points or points with no three collinear [Brass].
See [Matousek] for related results and questions.
[ABBCDHKLPW] Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila Pór, David R. Wood. Every Large Point Set contains Many Collinear Points or an Empty Pentagon, Graphs and Combinatorics 27(1): 47-60, 2011.
[AFKCW] Louigi Addario-Berry, Cristina Fernandes, Yoshiharu Kohayakawa, Jos Coelho de Pina, and Yoshiko Wakabayashi. On a geometric Ramsey-style problem, 2007.
[Brass] Peter Brass. On point sets without k collinear points. In Discrete Geometry, vol. 253 of Monographs and Textbooks in Pure and Applied Mathematics, pp. 185–192. Dekker, New York, 2003.
*[KPW] Jan Kára, Attila Pór, David R. Wood. On the chromatic number of the visibility graph of a set of points in the plane, Discrete and Computational Geometry 34(3):497-506, 2005.
[Matousek] Jiří Matoušek. Blocking visibility for points in general position, Discrete and Computational Geometry 42(2): 219-223, 2009.
* indicates original appearance(s) of problem.