Big line or big clique conjecture for planar point sets

From papers

Let PP be a finite set of points in the plane. Two distinct points v,wPv,w\in P are visible with respect to PP if

Pvw={v,w},P\cap\overline{vw}=\{v,w\},

where vw\overline{vw} is the closed line segment between vv and ww. The visibility graph of PP has vertex set PP, with two distinct points adjacent exactly when they are visible.

Big line or big clique conjecture. For all integers kk and \ell there is an integer nn such that every finite set of at least nn points in the plane contains either \ell collinear points or kk pairwise visible points; equivalently, its visibility graph contains a kk-clique.

This conjecture predicts a dichotomy between arbitrarily large collinear subsets and arbitrarily large cliques in the visibility graph of a planar point set. The source attributes it to KPW; its resolution is not established by the supplied context.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila Pór and David R. Wood, “Every Large Point Set contains Many Collinear Points or an Empty Pentagon”, arXiv:0904.0262 (2009).

Solutions 0

No solutions have been posted yet.