13 hours ago · Tech · hide · 0 comments

Reports that LLMs have killed the Erdős unit distance problem turn out to be greatly exaggerated. There is still plenty not yet understood about the problem. The problem asks, for \(n\) points in the Euclidean plane, how many pairs can be at unit distance from each other? When Paul Erdős posed the problem in 1946, he observed that the graph of unit distances cannot contain a subgraph of the form \(K_{2,3}\), a complete bipartite subgraph with two vertices on one side and three on the other. One way to see this is to draw unit circles through the two vertices on one side of a supposed \(K_{2,3}\) subgraph. These cross each other at most twice, and their two crossing points are the only points that can be vertices on the other side of the subgraph. Through reasoning later generalized as the Kővári–Sós–Turán theorem, Erdős observed that this forbidden subgraph implies an \(O(n^{3/2})\) upper bound on the number of unit distances. More generally, the Kővári–Sós–Turán theorem implies that…

No comments yet. Log in to reply on the Fediverse. Comments will appear here.