Gilbert-Pollak conjecture (Steiner ratio)

Description of constant

$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$.

Known upper bounds

Known lower bounds

Additional comments

• In 1968, Gilbert and Pollak conjectured that Steiner ratio is $\sqrt{3}/2\approx 0.866$, but this remains unproven. More information can be found at Wikipedia page on the Gilbert-Pollak conjecture.
• The $0.8559$ and $0.860$ bounds are computer-assisted results of the same kind: a finite set of per-region inequality certificates resting on a layer of human-proved geometric lemmas. [S2026] independently re-verified the [KHSHGW2026] certificate layer (330,193,755 records, zero failures) with clean-room software, then regenerated the partitions at the higher target using the same lemma set and verified all 1,104,177,103 resulting regions. Both bounds are conditional on the [KHSHGW2026] lemma layer.

References

• [GP1968] Gilbert, E. N. and Pollak, H. O. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1–29, 1968.
• [GH1976] Graham, R. L. and Hwang, F. K. Remarks on steiner minimal trees. Bull. Inst. Math. Acad. Sinica, 4(1):177–182, 1976.
• [CH1978] Chung, F. and Hwang, F. A lower bound for the steiner tree problem. SIAM Journal on Applied Mathematics, 34(1): 27–36, 1978.
• [DH1983] Du, D.-Z. and Hwang, F. K. A new bound for the steiner ratio. Transactions of the American Mathematical Society, 278(1):137–148, 1983.
• [CG1985] Chung, F. R. and Graham, R. L. A new bound for euclidean steiner minimal trees. Annals of the New York Academy of Sciences, 440(1):328–346, 1985.
• [KHSHGW2026] Ke, Y., Huang, T., Shu, Y., He, D., Gai, J., and Wang, L. Towards Solving the Gilbert-Pollak Conjecture via Large Language Models. arXiv:2601.22365. Preprint (2026).
• [S2026] Claude Fable 5 (Anthropic) and Savva, J. An Independent Verification of the Gilbert-Pollak Certificate Layer and a Certificate-Layer Bound of $0.860$ for the Steiner Ratio. doi:10.5281/zenodo.22223485. Preprint (2026). Code and data: github.com/aimathpapers/Steiner_Ratio.

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.