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 have many points that are all mutually visible to each other, with no third point blocking any two from seeing each other. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementFor any positive integers k and l there should exist another number n(k,l), such that every set of n(k,l) points contains l collinear points (a big line), k mutually visible points (a big clique), or both. 1 Proposed Year Progress Toward ResolutionUnsolved. Finite point sets in general position always contain a big clique, so it is true for l at most 3, and sets with no five mutually visible points contain many collinear points, so it is true for k at most 5. 1 Classification
Resolution Status Prize Status
Prize Status (category) Sources
1. Big-Line-Big-Clique Conjecture (Wikipedia)
Wikimedia FoundationLead section
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
Statement of the conjecture
For any positive integers k and ℓ there should exist another number n(k,ℓ), such that every set of n(k,ℓ) points contains ℓ collinear points (a 'big line'), k mutually visible points (a 'big clique'), or both.
History
The conjecture was introduced in 2005 by Jan Kára, Attila Pór, and David R. Wood
Partial results
Finite point sets in general position (no three collinear) do always contain a big clique, so the conjecture is true for ℓ ≤ 3.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.