Problem dossier · Graph Theory
No-three-in-line problem
How many points can be placed in an n×n grid with no three collinear? At most 2n (two per row), and 2n is achieved for all n up to at least 46 — but conjecturally only ~1.814n is possible for large n.
§1
Status
Open. Whether 2n is achievable for all n, and the true asymptotic constant, are both unknown.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
SAT/ILP and heuristic search for maximal configurations at n = 25–60; study the structure (symmetry groups) of record configurations to extrapolate constructions.
Tags: grid · collinear · extremal · sat · search
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Graph Theory and adjacent territory.
- Goemans' unsplittable-flow cost conjecture — Graph Theory
- Graffiti conjecture 284 — Graph Theory
- Caccetta–Häggkvist conjecture — Graph Theory
- Erdős–Faber–Lovász conjecture — Graph Theory
- Frankl's union-closed sets conjecture — Graph Theory
- Lonely runner conjecture — Graph Theory