Near-minimal spanning trees: A scaling exponent in probability models
- Author(s): Aldous, DJ;
- Bordenave, C;
- Lelarge, M
- et al.
Published Web Locationhttps://doi.org/10.1214/07-AIHP138
We study the relation between the minimal spanning tree (MST) on many random points and the "near-minimal" tree which is optimal subject to the constraint that a proportion 8 of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1 + 0 (δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the Euclidean model. © Association des Publications de l'Institut Henri Poincaré, 2008.