Connectivity of the three-dimensional minimal spanning forest
Give the nearest-neighbour edges of $\mathbb{Z}^3$ independent labels, uniform on $(0, 1)$, and let $F$ be the free minimal spanning forest: the subgraph of all edges that are not the edge of largest label in any finite simple cycle. On $\mathbb{Z}^d$ the free minimal spanning forest coincides with the wired one, the union of the invasion percolation trees grown from all vertices (Alexander; Lyons, Peres and Schramm). Alexander and Molchanov proved that on $\mathbb{Z}^2$ it is almost surely a tree. Newman and Stein, who related it to the ground states of a highly disordered spin-glass model, conjecture that it is a tree exactly when $d < 8$ or $d \le 8$; Jackson and Read suggest $6$ in place of $8$.
Problem. Is $F$ connected with probability one? Equivalently, does the infinite-volume minimal spanning forest of $\mathbb{Z}^3$ consist of a single spanning tree?
Source: Newman and Stein (1996), for ℤᵈ, who argue that the critical dimension is 8; see Lyons, Peres and Schramm (2006), §1, and Lyons and Peres (2016), Question 11.35. Stated for d = 3 by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, MP
- Keywords
- AIM Open Applied Problems, invasion percolation, minimal spanning forests
References
@article{newman1996,
author = {Newman, C. M. and Stein, D. L.},
title = {Ground-state structure in a highly disordered spin-glass model},
journal = {J. Statist. Phys.},
volume = {82},
number = {3-4},
year = {1996},
pages = {1113--1132},
doi = {10.1007/BF02179805},
eprint = {adap-org/9505005},
archivePrefix = {arXiv},
}
@article{lyons2006,
author = {Lyons, Russell and Peres, Yuval and Schramm, Oded},
title = {Minimal spanning forests},
journal = {Ann. Probab.},
volume = {34},
number = {5},
year = {2006},
pages = {1665--1692},
doi = {10.1214/009117906000000269},
eprint = {math/0412263},
archivePrefix = {arXiv},
}
@book{lyons2016,
author = {Lyons, Russell and Peres, Yuval},
title = {Probability on Trees and Networks},
series = {Cambridge Series in Statistical and Probabilistic Mathematics},
publisher = {Cambridge University Press},
address = {New York},
year = {2016},
doi = {10.1017/9781316672815},
}
@article{alexander1995,
author = {Alexander, Kenneth S.},
title = {Percolation and minimal spanning forests in infinite graphs},
journal = {Ann. Probab.},
volume = {23},
number = {1},
year = {1995},
pages = {87--104},
doi = {10.1214/aop/1176988378},
}
@article{alexander1994,
author = {Alexander, Kenneth S. and Molchanov, Stanislav A.},
title = {Percolation of level sets for two-dimensional random fields with lattice symmetry},
journal = {J. Statist. Phys.},
volume = {77},
number = {3-4},
year = {1994},
pages = {627--643},
doi = {10.1007/BF02179453},
}
@article{jackson2010,
author = {Jackson, T. S. and Read, N.},
title = {Theory of minimum spanning trees. {I}. {M}ean-field theory and strongly disordered spin-glass model},
journal = {Phys. Rev. E},
volume = {81},
number = {2},
year = {2010},
pages = {021130},
doi = {10.1103/PhysRevE.81.021130},
}
@misc{aim-three-dimensional-minimal-spanning-forest,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Connectivity of the three-dimensional minimal spanning forest}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/174-three-dimensional-minimal-spanning-forest.md},
note = {Entry 174 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00482, "Connectivity of the three-dimensional minimal spanning forest", clopen.solutions.