Big-line-big-clique conjecture

The big-line-big-clique conjecture is an unsolved problem in discrete geometry, stating that finite sets of many points in the Euclidean plane either have many collinear points, or they have many points that are all mutually visible to each other (no third point blocks any two of them from seeing each other).

Statement and history

More precisely, the big-line big-clique conjecture states that, for any positive integers $k$ and $\ell$ there should exist another number $n_{k,\ell }$ , such that every set of $n_{k,\ell }$ points contains $\ell$ collinear points (a "big line"), $k$ mutually-visible points (a "big clique"), or both.^[1]^[2]

The big-line-big-clique conjecture was posed by Jan Kára, Attila Pór, and David R. Wood in a 2005 publication.^[1]^[2] It has led to much additional research on point-to-point visibility in point sets.^[3]

Partial results

Finite point sets in general position (no three collinear) do always contain a big clique, so the conjecture is true for $\ell \leq 3$ . Additionally, finite point sets that have no five mutually-visible points (such as the intersections of the integer lattice with convex sets) do always contain many collinear points, so the conjecture is true for $k\leq 5$ .^[4]

Generalizing the integer lattice example, projecting a $d$ -dimensional system of lattice points of size $(\ell -1)\times (\ell -1)\times \cdots =(\ell -1)^{d}$ onto the plane, using a generic linear projection, produces a set of points with no $\ell$ collinear points and no $2^{d}+1$ mutually visible points. Therefore, when $n_{k,\ell }$ exists, it must be greater than $(\ell -1)^{\log _{2}(k-1)}$ .^[2]

Related problems

The visibilities among any system of points can be analyzed by using the visibility graph of the points, a graph that has the points as vertices and that connects two points by an edge whenever the line segment connecting them is disjoint from the other points. The "big cliques" of the big-line-big-clique conjecture are cliques in the visibility graph. However, although a system of points that is entirely collinear can be characterized by having a bipartite visibility graph, this characterization does not extend to subsets of points: a subset can have a bipartite induced subgraph of the visibility graph without being collinear.^[2]

According to the solution of the happy ending problem, every subset of points with no three in line includes a large subset forming the vertices of a convex polygon. More generally, it can be proven using the same methods that every set of sufficiently many points either includes $\ell$ collinear points or $k$ points in convex position. However, some of these pairs of convex points could be blocked from visibility by points within the convex polygon they form.^[2]

Another related question asks whether points in general position (or with no lines of more than some given number of points) contain the vertices of an empty convex polygon or hole. This is a polygon whose vertices belong to the point set, but that has no other points in the intersection of the point set with its convex hull. If a hole of a given size exists, its vertices all necessarily see each other. All sufficiently large sets of points in general position contain five vertices forming an empty pentagon^[4] or hexagon,^[5]^[6] but there exist arbitrarily large sets in general position with no empty heptagons.^[7]

A strengthening of the big line big clique conjecture asks for the big clique to be a "visible island", a set of points that are mutually visible and that are formed from the given larger point set by intersecting it with a convex set. However, this strengthened version is false: if a point set in general position has no empty heptagon, then replacing each of its points by a closely-spaced triple of collinear points produces a point set with no four in a line and with no visible islands of 13 or more points.^[8]

There is no possibility of an infinitary version of the same conjecture: Pór and Wood found examples of countable sets of points with no four points on a line and with no triangle of mutually visible points.^[9]

References

^ ^a ^b Ghosh, Subir Kumar; Goswami, Partha P. (2013), "Unsolved problems in visibility graphs of points, segments, and polygons", ACM Computing Surveys, 46 (2): 22:1–22:29, arXiv:1012.5187, doi:10.1145/2543581.2543589, S2CID 8747335
^ ^a ^b ^c ^d ^e Kára, Jan; Pór, Attila; Wood, David R. (2005), "On the chromatic number of the visibility graph of a set of points in the plane" (PDF), Discrete & Computational Geometry, 34 (3): 497–506, doi:10.1007/s00454-005-1177-z, MR 2160051, S2CID 7767717
^ Aloupis, Greg; Ballinger, Brad; Collette, Sébastien; Langerman, Stefan; Pór, Attila; Wood, David R. (2013), "Blocking colored point sets", in Pach, János (ed.), Thirty essays on geometric graph theory, New York: Springer, pp. 31–48, arXiv:1002.0190, doi:10.1007/978-1-4614-0110-0_4, MR 3205148, S2CID 2977893
^ ^a ^b Abel, Zachary; Ballinger, Brad; Bose, Prosenjit; Collette, Sébastien; Dujmović, Vida; Hurtado, Ferran; Kominers, Scott Duke; Langerman, Stefan; Pór, Attila; Wood, David R. (2011), "Every large point set contains many collinear points or an empty pentagon", Graphs and Combinatorics, 27 (1): 47–60, arXiv:0904.0262, doi:10.1007/s00373-010-0957-2, MR 2746833, S2CID 6780708
^ Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete & Computational Geometry, 38 (2): 389–397, doi:10.1007/s00454-007-1343-6
^ Gerken, Tobias (2008), "Empty convex hexagons in planar point sets", Discrete & Computational Geometry, 39 (1–3): 239–272, doi:10.1007/s00454-007-9018-x
^ Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26 (4): 482–484, doi:10.4153/CMB-1983-077-8, MR 0716589, S2CID 120267029
^ Leuchtner, Sophie; Nicolás, Carlos M.; Suk, Andrew (2022), "A note on visible islands", Studia Scientiarum Mathematicarum Hungarica, 59 (2): 160–163, arXiv:2109.00022, doi:10.1556/012.2022.01524, MR 4484538, S2CID 246017003
^ Pór, Attila; Wood, David R. (August 2010), The big-line-big-clique conjecture is false for infinite point sets, arXiv:1008.2988

[gg-1] Ghosh, Subir Kumar; Goswami, Partha P. (2013), "Unsolved problems in visibility graphs of points, segments, and polygons", ACM Computing Surveys, 46 (2): 22:1–22:29, arXiv:1012.5187, doi:10.1145/2543581.2543589, S2CID 8747335

[kpw-2] Kára, Jan; Pór, Attila; Wood, David R. (2005), "On the chromatic number of the visibility graph of a set of points in the plane" (PDF), Discrete & Computational Geometry, 34 (3): 497–506, doi:10.1007/s00454-005-1177-z, MR 2160051, S2CID 7767717

[abc-3] Aloupis, Greg; Ballinger, Brad; Collette, Sébastien; Langerman, Stefan; Pór, Attila; Wood, David R. (2013), "Blocking colored point sets", in Pach, János (ed.), Thirty essays on geometric graph theory, New York: Springer, pp. 31–48, arXiv:1002.0190, doi:10.1007/978-1-4614-0110-0_4, MR 3205148, S2CID 2977893

[abb-4] Abel, Zachary; Ballinger, Brad; Bose, Prosenjit; Collette, Sébastien; Dujmović, Vida; Hurtado, Ferran; Kominers, Scott Duke; Langerman, Stefan; Pór, Attila; Wood, David R. (2011), "Every large point set contains many collinear points or an empty pentagon", Graphs and Combinatorics, 27 (1): 47–60, arXiv:0904.0262, doi:10.1007/s00373-010-0957-2, MR 2746833, S2CID 6780708

[n-5] Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete & Computational Geometry, 38 (2): 389–397, doi:10.1007/s00454-007-1343-6

[g-6] Gerken, Tobias (2008), "Empty convex hexagons in planar point sets", Discrete & Computational Geometry, 39 (1–3): 239–272, doi:10.1007/s00454-007-9018-x

[h-7] Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26 (4): 482–484, doi:10.4153/CMB-1983-077-8, MR 0716589, S2CID 120267029

[lns-8] Leuchtner, Sophie; Nicolás, Carlos M.; Suk, Andrew (2022), "A note on visible islands", Studia Scientiarum Mathematicarum Hungarica, 59 (2): 160–163, arXiv:2109.00022, doi:10.1556/012.2022.01524, MR 4484538, S2CID 246017003

[pw-9] Pór, Attila; Wood, David R. (August 2010), The big-line-big-clique conjecture is false for infinite point sets, arXiv:1008.2988

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]