The six-point MST-ratio conjecture for planar point sets

About 3 years old · traced to

Let PP be a set of nn points in the plane. Write w(P)w(P) for the length of a Euclidean minimum spanning tree of PP, and let

γ(P)=max⁡P=R∪Bw(R)+w(B)w(P),\gamma(P)=\max_{P=R\cup B}\frac{w(R)+w(B)}{w(P)},

where the maximum is over all non-trivial bipartitions of PP into two sets. Six-point MST-ratio conjecture. For any set PP of n≥6n\geq 6 points in the plane, we have γ(P)>1\gamma(P)>1. This would improve the paper's established guarantee from n≥12n\geq 12 to n≥6n\geq 6; the conjecture is presented as an open question in the source.

References

Primary source

Adrian Dumitrescu, János Pach and Géza Tóth, “Two trees are better than one”, arXiv:2312.09916 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.