Erdős #99 — must a min-diameter unit-min-distance set contain a unit triangle?

Statement

Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with minimum distance equal to $1$, chosen to minimise the diameter of $A$. If $n$ is sufficiently large, must there be three points in $A$ which form an equilateral triangle of side $1$?

(Equivalently: does every diameter-minimizing configuration, for large $n$, contain a $3$-clique in its minimum-distance graph — i.e. three mutually pairwise-unit-distance points?)

Facts

- Prize \$100 for a counterexample; Erdős offered only \$50 for a proof [Er94b] — he expected it to be true and easy, and was surprised when B. H. Sendov and M. Simonovits doubted it (erdosproblems.com/99, quoting [Er94b]). - Status open. erdosproblems.com's own tooltip: "This is open, and cannot be resolved with a finite computation" — it is a statement for all sufficiently large $n$, so falsifiability is not-finite (a single finite counterexample at some large $n$ would only be a genuine disproof if that $n$ is provably "sufficiently large"; small-$n$ counterexamples are already known and excluded by the "sufficiently large" hedge). - The naive statement is already false for $n=4$: the unit square is a diameter-minimizing 4-point set with min distance 1 and contains no equilateral triangle (two unit equilateral triangles glued along an edge is another optimal 4-point config, and does contain one) — hence the "sufficiently large $n$" qualifier is load-bearing (erdosproblems.com/99). - Behavior for small $n$ studied by Bezdek & Fodor, "Minimal diameter of certain sets in the plane," J. Combin. Theory Ser. A 85 (1999), 105–111 [BeFo99] (erdosproblems.com/bibs/BeFo99) — they characterize/enumerate diameter-minimizing unit-min-distance configurations for small $n$ (this is the finite-computation regime; it does not touch "sufficiently large $n$"). - Origin refs: Erdős, "Some problems in number theory, combinatorics and combinatorial geometry," Math. Pannon. (1994), 261–269 [Er94b]; "Some of my favourite problems in number theory, combinatorics, and geometry," Resenhas (1995), 165–186 [Er95]; "Some of my favourite unsolved problems," Math. Japon. (1997), 527–537 [Er97e]. - Intuition Erdős gives [Er94b] (quoted on erdosproblems.com/99): Thue proved the minimal-diameter configurations are asymptotically achieved by points of the triangular lattice intersected with a disk; Erdős believed the extremal sets must have very large — perhaps $(1-o(1))n$ — intersection with the triangular lattice. The equilateral-triangle question is the natural first, weaker consequence of that stronger structural belief. - Directly related sibling problem: erdos/103 — let $h(n)$ count the number of *incongruent* diameter-minimizing $n$-point unit-min-distance sets; is $h(n)\to\infty$? erdosproblems.com/103 explicitly cross-links to #99 ("See also [99]") and states plainly: "no solutions, partial or complete, claimed in the comments," and "it is not even known whether $h(n)\geq 2$ for all large $n$." Confirms this whole problem family is essentially untouched. - Formalized in Lean: google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/99.lean states erdos_99 with answer(sorry), tag @[category research open, AMS 52] — i.e. DeepMind's own formal-conjectures project (as of the file's 2026 copyright header) treats it as unresolved, not merely un-formalized. - Known results / best bounds: none found for the actual conjecture. No paper claiming a proof, disproof, or asymptotic partial result for #99 turned up in arXiv/Semantic Scholar/Google-Scholar-via-search searches ("minimal diameter set points plane equilateral triangle Erdős", "diameter graphs Erdős triangles", "spreading points minimum distance diameter"). The closest adjacent *general theory* is the machinery below. - Do not confuse with a same-named, different Erdős conjecture: arXiv:2604.15305, Boon Suan Ho, "Erdős's diameter conjecture for separated distances fails in high dimensions" (2026) — this refutes the *unrelated* Erdős asymptotic bound "every $n$-point set in $\mathbb{R}^d$ with pairwise distances $\geq 1$ has diameter $\geq(1+o(1))n^2$" for large $d$, via an explicit construction for every prime power $q$ of $q+1$ points in $\mathbb{R}^{q^2+q}$ (built from finite-geometry/incidence-vector combinatorics) with diameter $\leq(1-1/\pi^2+o(1))n^2$. It is a genuine, recent (2026) disproof of a "diameter conjecture," but of a *different, high-dimensional, unconstrained-$n$* statement — not of #99 (which is 2D, fixes the extremal-configuration selection rule, and asks about internal triangle structure, not a global diameter bound). Flagging this explicitly because the names are easy to conflate. - Related problems: erdos/103.

Literature state

Not resolved anywhere found. Three independent confirmations of "still open": (1) erdosproblems.com/99 itself, actively maintained, marked OPEN with no unincorporated forum solutions; (2) the sibling erdosproblems.com/103 explicitly says no partial/complete solutions have been claimed for the whole family; (3) the DeepMind formal-conjectures Lean file has the theorem statement but sorry, tagged research open. No arXiv paper, survey, or AI-system announcement (GPT/DeepMind/Aristotle) claiming progress on this specific statement was found in this search.

The relevant *general* literature is about the two graphs one can build on a finite point set at its two extreme distances, and both have mature, largely-solved combinatorial theories that supply technique but not (yet) an answer: - Minimum-distance graphs (join points at exactly the minimum distance — this is precisely the graph whose triangles/3-cliques Erdős #99 asks about): classical fact that they are always planar in the Euclidean plane (no two minimum-distance edges can cross), and Harborth (1974), answering a question of Reutter, proved the sharp maximum-edge bound $m(n,\mathbb{E}^2) = 3n - O(\sqrt n)$ — surveyed in Swanepoel, "Combinatorial distance geometry in normed spaces," arXiv:1702.00066, §4.1. This planarity + near-triangulation edge density is exactly the structural lever that would need to be pushed to force a 3-clique. - Diameter graphs (the dual object: join points at the *maximum* distance) have a fully resolved edge-count theory: the Vázsonyi conjecture (max $2n-2$ edges for $n\geq4$ points in $\mathbb{R}^3$) was proved independently by Grünbaum, Heppes, and Straszewicz via convexity/ball-polytope arguments, and Swanepoel gave a shorter, more elementary proof avoiding ball polytopes in "A new proof of Vázsonyi's conjecture," arXiv:0705.0606 — surveyed in the same §5 of arXiv:1702.00066. This shows the "extremal graph on extreme-distance pairs" style of problem is very tractable when the target graph is the *diameter* graph rather than the min-distance graph; #99 is the harder, min-distance-graph analogue. - Thue's theorem (triangular-lattice packing is asymptotically optimal for minimal-diameter unit-min-distance sets) is the structural anchor Erdős's own intuition rests on (per [Er94b], quoted on erdosproblems.com/99); the rigorous general form of "hexagonal/triangular lattice is the densest circle packing" is due to Thue (1910) with the first fully rigorous proof by L. Fejes Tóth (via a Dirichlet-cell / isoperimetric area-lower-bound argument — each packing cell has area $\geq$ the regular-hexagon cell of the same inradius), discussed in the survey "Five Essays on the Geometry of László Fejes Tóth," arXiv:1604.02776. This gives the *asymptotic-density* argument but not (by itself) the *pointwise* triangle-existence claim #99 needs. - Adjacent solved extremal-point-set results using computer-assisted case analysis (a template for how a "sufficiently large $n$" 2D extremal-configuration claim in this family *has* been fully closed elsewhere): Fabila-Monroy, Hidalgo-Toscano, Leaños, Lomelí-Haro, "Optimal point sets determining few distinct triangles," arXiv:1609.00206 — prove exactly $F(1)=4$, $F(2)=5$ (max points determining $t$ distinct triangles) with a matching general bound $F(t)<48(t+1)$; follow-up "Uniqueness of Optimal Point Sets Determining Two Distinct Triangles," arXiv:1910.00629, pins down the extremal configuration exactly. These are proof-of-concept that small-parameter "optimal planar point configuration" questions in this exact family (extremal distance/triangle-count problems) are closable with a mix of structural convexity arguments and exhaustive/computer-assisted case checking — the same toolkit that would need to scale to "for all sufficiently large $n$" to hit #99, which is the actual obstruction (their $t$ is fixed/finite; #99's $n\to\infty$ is not).

Attack surface

- Mode: derivation + formalization (not finite-search for the full claim — erdosproblems.com is explicit that no finite computation settles "for all sufficiently large $n$"; but bounded sub-instances ARE finite-search and useful as evidence/oracle-building). - Concrete first experiment: reproduce and extend Bezdek–Fodor [BeFo99] computationally — for each $n$ from (say) 4 to ~30, use nonlinear optimization / branch-and-bound (or a CP-SAT relaxation over a fine grid + local continuous refinement) to find the exact diameter-minimizing unit-min-distance configuration(s), then mechanically check each for a 3-clique in its minimum-distance graph (three points pairwise at distance exactly 1, within numerical tolerance, then certified via exact/interval arithmetic). This won't prove the "sufficiently large $n$" claim but (a) tells us the smallest $n$ (if any) past the known $n=4$ exception where the property could plausibly start holding forever, (b) generates the data needed to attack sibling problem erdos/103 ($h(n)$, counting incongruent optima) simultaneously, and (c) stress-tests whether the extremal configurations are really converging to triangular-lattice patches as Thue's theorem/Erdős's intuition suggests. - Oracle: for fixed $n$, a candidate configuration is mechanically verifiable — check all pairwise distances $\geq 1$ (with equality achieved), compute the diameter, and compare against a certified lower bound on the true minimum diameter (from a packing/SDP relaxation or exhaustive branch-and-bound with rigorous interval arithmetic) to confirm global optimality; triangle presence/absence is then a trivial distance check on the (already verified) optimum. - Feasibility: honest read — a genuine open problem in a mature but stubborn subfield, not in reach for a direct proof. The 2D minimal-diameter / minimum-distance-graph theory is well-developed (planarity, Harborth's edge bound) but nobody has connected it to a forced-triangle theorem, and the sibling #103 shows even "$h(n)\geq 2$ eventually" is unknown — a much weaker structural question than #99's. Realistic near-term contribution: (1) the finite computational sub-experiment above (concrete, finishable, produces citable/checkable data extending [BeFo99]'s known range), or (2) formalizing the finite Bezdek–Fodor small-$n$ results in the existing Lean stub as a stepping stone, not the full "sufficiently large $n$" theorem.

Related

- erdos/103 — sibling problem on the same class of diameter-minimizing unit-min-distance configurations: does $h(n)$, the number of incongruent optima, tend to $\infty$? Cross-linked "See also" on erdosproblems.com both directions; equally open, equally no comments/partial solutions on record. - concept/minimum-distance-graph — the graph joining points at exactly the minimum (unit) distance; always planar in $\mathbb{E}^2$; sharp edge bound $3n-O(\sqrt n)$ (Harborth 1974, surveyed arXiv:1702.00066 §4.1). #99 is literally "must this graph, on a diameter-minimizing vertex set, contain a triangle?" - concept/diameter-graph — the dual graph joining points at the *maximum* distance; Vázsonyi conjecture (edge bound $2n-2$ in $\mathbb{R}^3$) fully proved (Grünbaum/Heppes/Straszewicz; simplified proof by Swanepoel, arXiv:0705.0606) — a fully-solved analogue showing the extreme-distance-graph style of question is tractable on the diameter side. - concept/triangular-lattice-packing — Thue's theorem (triangular lattice = asymptotically optimal circle packing), rigorously proved via L. Fejes Tóth's Dirichlet-cell isoperimetric argument (arXiv:1604.02776); the structural belief underlying Erdős's own intuition for #99. - concept/extremal-point-set-computer-search — the computer-assisted exhaustive/structural technique that fully closed the neighbouring "optimal point sets determining few distinct triangles" problem for fixed small parameters (arXiv:1609.00206, arXiv:1910.00629) — the template for finite sub-experiments on #99, though it does not scale to "all sufficiently large $n$" by itself.