alt Hacker NewsI would have thought a triangular grid works better than a grid of squares. You get ~3n links vs ~2n for the square grid. Curious what the AI came up with.
Replies
bustermellotron • yesterday at 8:36 PM
The grid of squares actually gets > Cn for any C. (More in fact… C can grow like n^a/loglog(n).) The AI proved > n^{1 + b} for some small b > 0, which a human (Will Sawin) has now proved can be about b = 0.014. The grid can be rescaled so the edges are not necessarily length 1, but other pairs will have length 1; that is necessary to get more than 2n unit distances.
kilotaras • yesterday at 8:20 PM
Both 3n and 2n are linear, the broken conjecture is that you can't do better than linear.
Yes, not providing visualization of the solution seems criminal.