View source for Big-line-big-clique conjecture

{{Short description|Unsolved problem in discrete geometry}}
{{Use dmy dates|cs1-dates=ly|date=February 2023}}
{{Use list-defined references|date=February 2023}}
[[File:Convex_grid_subset.svg|thumb|upright=1.2|The blue points have big lines of up to ten points, but no big clique (the largest mutually-visible subsets of any convex grid subset have only four points). The yellow points form a big clique of ten points, but have no big line (the largest collinear subset of points in convex position has only two points). According to the big-line-big-clique conjecture, no point set can avoid both big lines and big cliques.]]
The '''big-line-big-clique conjecture''' is an unsolved problem in [[discrete geometry]], stating that [[finite set]]s of many points in the [[Euclidean plane]] either have many [[collinearity|collinear points]], or they have many points that are [[Visibility graph|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 <math>k</math> and <math>\ell</math> there should exist another number <math>n_{k,\ell}</math>, such that every set of <math>n_{k,\ell}</math> points contains <math>\ell</math> collinear points (a "big line"), <math>k</math> mutually-visible points (a "big clique"), or both.{{r|gg|kpw}}

The big-line-big-clique conjecture was posed by Jan Kára, Attila Pór, and [[David Wood (mathematician)|David R. Wood]] in a 2005 publication.{{r|gg|kpw}} It has led to much additional research on point-to-point visibility in point sets.{{r|abc}}

==Partial results==
Finite point sets in [[general position]] (no three collinear) do always contain a big clique, so the conjecture is true for <math>\ell\le 3</math>. 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 <math>k\le 5</math>.{{r|abb}}

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

==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 [[Clique (graph theory)|cliques]] in the visibility graph. However, although a system of points that is entirely collinear can be characterized by having a [[bipartite graph|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.{{r|kpw}}

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 <math>\ell</math> collinear points or <math>k</math> 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.{{r|kpw}}

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]]{{r|abb}} or [[hexagon]],{{r|n|g}} but there exist arbitrarily large sets in general position with no empty [[heptagon]]s.{{r|h}}

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.{{r|lns}}

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.{{r|pw}}

==References==
{{reflist|refs=

<ref name=abb>{{citation
 | last1 = Abel | first1 = Zachary
 | last2 = Ballinger | first2 = Brad
 | last3 = Bose | first3 = Prosenjit | author3-link = Jit Bose
 | last4 = Collette | first4 = Sébastien
 | last5 = Dujmović | first5 = Vida | author5-link = Vida Dujmović
 | last6 = Hurtado | first6 = Ferran | author6-link = Ferran Hurtado
 | last7 = Kominers | first7 = Scott Duke
 | last8 = Langerman | first8 = Stefan | author8-link = Stefan Langerman
 | last9 = Pór | first9 = Attila
 | last10 = Wood | first10 = David R. | author10-link = David Wood (mathematician)
 | arxiv = 0904.0262
 | doi = 10.1007/s00373-010-0957-2
 | issue = 1
 | journal = [[Graphs and Combinatorics]]
 | mr = 2746833
 | pages = 47–60
 | title = Every large point set contains many collinear points or an empty pentagon
 | volume = 27
 | year = 2011| s2cid = 6780708
 }}</ref>

<ref name=abc>{{citation
 | last1 = Aloupis | first1 = Greg
 | last2 = Ballinger | first2 = Brad
 | last3 = Collette | first3 = Sébastien
 | last4 = Langerman | first4 = Stefan | author4-link = Stefan Langerman
 | last5 = Pór | first5 = Attila
 | last6 = Wood | first6 = David R. | author6-link = David Wood (mathematician)
 | editor-last = Pach | editor-first = János | editor-link = János Pach
 | arxiv = 1002.0190
 | contribution = Blocking colored point sets
 | doi = 10.1007/978-1-4614-0110-0_4
 | location = New York
 | mr = 3205148
 | pages = 31–48
 | publisher = Springer
 | title = Thirty essays on geometric graph theory
 | year = 2013| s2cid = 2977893
 }}</ref>

<ref name=g>{{citation
 | last = Gerken | first = Tobias
 | doi = 10.1007/s00454-007-9018-x | doi-access = free
 | issue = 1–3
 | journal = [[Discrete & Computational Geometry]]
 | pages = 239–272
 | title = Empty convex hexagons in planar point sets
 | volume = 39
 | year = 2008}}</ref>

<ref name=gg>{{citation
 | last1 = Ghosh | first1 = Subir Kumar
 | last2 = Goswami | first2 = Partha P.
 | arxiv = 1012.5187
 | doi = 10.1145/2543581.2543589
 | issue = 2
 | journal = ACM Computing Surveys
 | pages = 22:1–22:29
 | title = Unsolved problems in visibility graphs of points, segments, and polygons
 | volume = 46
 | year = 2013| s2cid = 8747335
 }}</ref>

<ref name=h>{{citation
 | last = Horton | first = J. D.
 | doi = 10.4153/CMB-1983-077-8
 | issue = 4
 | journal = [[Canadian Mathematical Bulletin]]
 | mr = 716589
 | pages = 482–484
 | title = Sets with no empty convex 7-gons
 | volume = 26
 | year = 1983| s2cid = 120267029
 | doi-access = free
 }}</ref>
 
<ref name=kpw>{{citation
 | last1 = Kára | first1 = Jan
 | last2 = Pór | first2 = Attila
 | last3 = Wood | first3 = David R. | author3-link = David Wood (mathematician)
 | doi = 10.1007/s00454-005-1177-z
 | issue = 3
 | journal = [[Discrete & Computational Geometry]]
 | mr = 2160051
 | pages = 497–506
 | title = On the chromatic number of the visibility graph of a set of points in the plane
 | url = http://users.monash.edu/~davidwo/papers/KPW-VisCol-DCG05.pdf
 | volume = 34
 | year = 2005| s2cid = 7767717
 }}</ref>

<ref name=lns>{{citation
 | last1 = Leuchtner | first1 = Sophie
 | last2 = Nicolás | first2 = Carlos M.
 | last3 = Suk | first3 = Andrew
 | arxiv = 2109.00022
 | doi = 10.1556/012.2022.01524
 | issue = 2
 | journal = Studia Scientiarum Mathematicarum Hungarica
 | mr = 4484538
 | pages = 160–163
 | title = A note on visible islands
 | volume = 59
 | year = 2022| s2cid = 246017003
 }}</ref>

<ref name=n>{{citation
 | last = Nicolás | first = Carlos M.
 | doi = 10.1007/s00454-007-1343-6 | doi-access = free
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | pages = 389–397
 | title = The empty hexagon theorem
 | volume = 38
 | year = 2007}}</ref>

<ref name=pw>{{citation
 | last1 = Pór | first1 = Attila
 | last2 = Wood | first2 = David R. | author2-link = David Wood (mathematician)
 | arxiv = 1008.2988
 | date = August 2010
 | title = The big-line-big-clique conjecture is false for infinite point sets}}</ref>

}}

[[Category:Conjectures]]
[[Category:Discrete geometry]]