Near-minimal spanning trees : a scaling exponent in probability models
Annales de l'I.H.P. Probabilités et statistiques, Volume 44 (2008) no. 5, p. 962-976

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 δ 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+Θ(δ 2 ). We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.

Nous étudions la relation entre l’arbre couvrant minimal (ACM) sur des points aléatoires et l’arbre «quasi» optimal sous la contrainte qu’une proportion δ de ses arêtes soit différente de celles de l’ACM. Un raisonnement heuristique suggère que quelque soit le modèle probabiliste sous-jacent, le ratio des longueurs des deux arbres doit varier en 1+Θ(δ 2 ). Nous montrons ce résultat d'échelle pour le modèle de la grille avec des longueurs d'arêtes aléatoires et pour le modèle euclidien.

DOI : https://doi.org/10.1214/07-AIHP138
Classification:  05C80,  60K35,  68W40
Keywords: combinatorial optimization, continuum percolation, disordered lattice, local weak convergence, minimal spanning tree, Poisson point process, probabilistic analysis of algorithms, random geometric graph
@article{AIHPB_2008__44_5_962_0,
     author = {Aldous, David J. and Bordenave, Charles and Lelarge, Marc},
     title = {Near-minimal spanning trees : a scaling exponent in probability models},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {44},
     number = {5},
     year = {2008},
     pages = {962-976},
     doi = {10.1214/07-AIHP138},
     zbl = {1186.05108},
     mrnumber = {2453778},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2008__44_5_962_0}
}
Aldous, David J.; Bordenave, Charles; Lelarge, Marc. Near-minimal spanning trees : a scaling exponent in probability models. Annales de l'I.H.P. Probabilités et statistiques, Volume 44 (2008) no. 5, pp. 962-976. doi : 10.1214/07-AIHP138. http://www.numdam.org/item/AIHPB_2008__44_5_962_0/

[1] D. J. Aldous and A. G. Percus. Scaling and universality in continuous length combinatorial optimization. Proc. Natl. Acad. Sci. USA 100 (2003) 11211-11215. | MR 2007286 | Zbl 1063.90041

[2] D. J. Aldous. The ζ(2) limit in the random assignment problem. Random Structures Algorithms 18 (2001) 381-418. | MR 1839499 | Zbl 0993.60018

[3] D. J. Aldous and J. M. Steele. Asymptotics for Euclidean minimal spanning trees on random points. Probab. Theory Related Fields 92 (1992) 247-258. | MR 1161188 | Zbl 0767.60005

[4] D. J. Aldous and J. M. Steele. The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures 1-72. H. Kesten (Ed.). Springer, Berlin, 2003. | MR 2023650 | Zbl 1037.60008

[5] K. S. Alexander. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995) 87-104. | MR 1330762 | Zbl 0827.60079

[6] K. S. Alexander. Simultaneous uniqueness of infinite clusters in stationary random labeled graphs. Comm. Math. Phys. 168 (1995) 39-55. | MR 1324390 | Zbl 0827.60080

[7] G. Chartrand and L. Lesniak. Graphs and Digraphs, 2nd edition. Wadsworth, Monterey, CA, 1986. | MR 834583 | Zbl 0666.05001

[8] L. P. Kadanoff. Statistical Physics. World Scientific, River Edge, NJ, 2000. | MR 1772071 | Zbl 0952.82001

[9] W. Krauth and M. Mézard. The cavity method and the travelling-salesman problem. Europhys. Lett. 8 (1989) 213-218.

[10] R. Meester and R. Roy. Continuum Percolation. Cambridge Univ. Press, 1996. | MR 1409145 | Zbl 0858.60092

[11] J. M. Steele. Probability Theory and Combinatorial Optimization. SIAM, Philadelphia, PA, 1997. | MR 1422018 | Zbl 0916.90233

[12] M. Penrose and J. E. Yukich. Weak laws of large numbers in geometric probability. Ann. Appl. Probab. 13 (2003) 277-303. | MR 1952000 | Zbl 1029.60008

[13] J. E. Yukich. Probability Theory of Classical Euclidean Optimization Problems. Springer, Berlin, 1998. | MR 1632875 | Zbl 0902.60001