Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Abhijeet Khopkar, Edge complexity of geometric graphs on convex independent point sets, arXiv:1605.08066, first posted 2016-05-24 and revised 2017-04-21. Its abstract says that unit distance graphs on convexly independent point sets have O(n)O(n) edges, improving the known O(nlog⁡n)O(n\log n), and its Theorem 4 states that bound; this is the positive answer to Problem 96. The paper's main subject is the locally Gabriel graphs that contain the unit distance graphs, for which it gives a simpler proof of the bound 2nlog⁡n+O(n)2n\log n+O(n).

Rejected. The claim is contradicted by the certified disproof on [[problems/distance_problems/E0096/claims/2026_09_10_kruer_kohlmeyer|Kruer and Kohlmeyer's page]], whose exposition says that its theorem contradicts the asserted bound and that it does not locate the erroneous step. The preprint carries no journal reference on its arXiv record as of 2026-10-07. When it was raised in the problem's discussion thread on 2026-01-13, a reader reported that a lemma on which it rests makes a choice without the verification it needs, and on 2026-06-17 another reported that the text does not contain a proof of Theorem 4; the site kept the problem labeled open.