Near-minimal spanning trees : a scaling exponent in probability models
Aldous, David J. ; Bordenave, Charles ; Lelarge, Marc
Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008), p. 962-976 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

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.

Publié le : 2008-01-01
DOI : https://doi.org/10.1214/07-AIHP138
Classification:  05C80,  60K35,  68W40 
@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},
     volume = {44},
     year = {2008},
     pages = {962-976},
     doi = {10.1214/07-AIHP138},
     mrnumber = {2453778},
     zbl = {1186.05108},
     language = {en},
     url = {http://dml.mathdoc.fr/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, Tome 44 (2008) pp. 962-976. doi : 10.1214/07-AIHP138. http://gdmltest.u-ga.fr/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