Submit progress

on Gilbert-Pollak conjecture (Steiner ratio) ($C_{43}$)

The statement

$C_{43}$ is defined as the infimum of the ratio of the length of the Steiner Minimal Tree to the length of the Euclidean Minimum Spanning Tree over all finite sets of points $V \subseteq \mathbb{R}^2$ : $C_{43} = \inf_{V}L_S(V)/L_M(V)$ , where $L_S(V)$ and $L_M(V)$ denote the lengths of Steiner Minimal Tree and Minimum Spanning Tree, respectively.

Consider a set $V$ of $n$ points in the Euclidean plane $\mathbb{R}^2$ . A spanning tree on $V$ is a connected, acyclic graph with vertex set $V$ . When the length of each edge is defined as the Euclidean distance between its endpoints, a spanning tree that minimizes the total length is called a Minimum Spanning Tree. The shortest network interconnecting all points in $V$ , where the length of each edge is measured by Euclidean distance, is necessarily a tree, referred to as a Steiner Minimal Tree. A Steiner Minimal Tree may contain auxiliary vertices not in $V$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.