MathDBLinear lower-bound conjecture for the bicolored MST crossing number
Linear lower-bound conjecture for the bicolored MST crossing number
Let be a generic set of points in the plane. The linear lower-bound conjecture.
The authors identify this as the most important problem for improving the lower bound for generic point sets. It would make the currently linear upper bound asymptotically tight, but no resolution is given.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Todor Antić, Morteza Saghafian, Maria Saumell, Felix Schröder, Josef Tkadlec and Pavel Valtr, “How many times can two minimum spanning trees cross?”, arXiv:2601.20060 (2026).
Additional references
13 papers in this index state this conjecture (2012–2026). The statement above is taken from the most recent of them; the others are arXiv:2509.10941, arXiv:2509.09895, arXiv:2501.03234, arXiv:2209.01447, arXiv:2203.12006, arXiv:2007.08324, arXiv:1811.08532, arXiv:1805.05204, arXiv:1312.1724, arXiv:1311.5051, arXiv:1303.4580, arXiv:1212.6756.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.