The big-line-big-clique conjecture is an unsolved problem in

discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geom ...

, stating that

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, is a finite set with five elements. Th ...

s of many points in the

Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...

either have many

collinear points In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned ...

, 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_

, such that every set of

n_

points contains

\ell

collinear points (a "big line"),

k

mutually-visible points (a "big clique"), or both. The big-line-big-clique conjecture was posed by Jan Kára, Attila Pór, and David R. Wood in a 2005 publication. It has led to much additional research on point-to-point visibility in point sets.

Partial results

Finite point sets in

general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that a ...

(no three collinear) do always contain a big clique, so the conjecture is true for

\ell\le 3

. Additionally, finite point sets that have no five mutually-visible points (such as the intersections of the

integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice (group), lattice in the Euclidean space whose lattice points are tuple, -tuples of integers. The two-dimensional integer lattice is also called the s ...

with convex sets) do always contain many collinear points, so the conjecture is true for

k\le 5

. 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_

exists, it must be greater than

(\ell-1)^

Related problems

The visibilities among any system of points can be analyzed by using the

visibility graph In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge re ...

of the points, a graph that has the points as vertices and that connects two points by an edge whenever the

line segment In geometry, a line segment is a part of a line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...

connecting them is disjoint from the other points. The "big cliques" of the big-line-big-clique conjecture are

cliques A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...

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 In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

of the visibility graph without being collinear. 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 In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is ...

. 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 In discrete and computational geometry, a set of points in the Euclidean plane or a higher-dimensional Euclidean space is said to be in convex position or convex independent if none of the points can be represented as a convex combination of the ot ...

. However, some of these pairs of convex points could be blocked from visibility by points within the convex polygon they form. 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 In geometry, a pentagon () is any five-sided polygon or 5-gon. The sum of the internal angles in a simple polygon, simple pentagon is 540°. A pentagon may be simple or list of self-intersecting polygons, self-intersecting. A self-intersecting ...

hexagon In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A regular hexagon is de ...

, but there exist arbitrarily large sets in general position with no empty

heptagon In geometry, a heptagon or septagon is a seven-sided polygon or 7-gon. The heptagon is sometimes referred to as the septagon, using ''Wikt:septa-, septa-'' (an elision of ''Wikt:septua-, septua-''), a Latin-derived numerical prefix, rather than ...

s. 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. There is no possibility of an

infinitary In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values. In standard mathematics, an operati ...

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.

References

{{reflist, refs= {{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 ''Graphs and Combinatorics'' (ISSN 0911-0119, abbreviated ''Graphs Combin.'') is a peer-reviewed academic journal in graph theory, combinatorics, and discrete geometry published by Springer Japan. Its editor-in-chief is Katsuhiro Ota of Keio Univ ...

, mr = 2746833 , pages = 47–60 , title = Every large point set contains many collinear points or an empty pentagon , volume = 27 , year = 2011, s2cid = 6780708 {{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, isbn = 978-1-4614-0109-4 , s2cid = 2977893 {{citation , last = Gerken , first = Tobias , doi = 10.1007/s00454-007-9018-x , doi-access = free , issue = 1–3 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...

, pages = 239–272 , title = Empty convex hexagons in planar point sets , volume = 39 , year = 2008 {{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 {{citation , last = Horton , first = J. D. , doi = 10.4153/CMB-1983-077-8 , issue = 4 , journal =

Canadian Mathematical Bulletin The ''Canadian Mathematical Bulletin'' () is a mathematics journal, established in 1958 and published quarterly by the Canadian Mathematical Society. The current editors-in-chief of the journal are Antonio Lei and Javad Mashreghi. The journal p ...

, mr = 716589 , pages = 482–484 , title = Sets with no empty convex 7-gons , volume = 26 , year = 1983, s2cid = 120267029 , doi-access = free {{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 =

, 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 {{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 {{citation , last = Nicolás , first = Carlos M. , doi = 10.1007/s00454-007-1343-6 , doi-access = free , issue = 2 , journal =

, pages = 389–397 , title = The empty hexagon theorem , volume = 38 , year = 2007 {{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 Conjectures Discrete geometry