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.

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: 10.1214/07-AIHP138
Classification: 05C80, 60K35, 68W40
Mots-clés : 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},
     pages = {962--976},
     publisher = {Gauthier-Villars},
     volume = {44},
     number = {5},
     year = {2008},
     doi = {10.1214/07-AIHP138},
     mrnumber = {2453778},
     zbl = {1186.05108},
     language = {en},
     url = {https://www.numdam.org/articles/10.1214/07-AIHP138/}
}
TY  - JOUR
AU  - Aldous, David J.
AU  - Bordenave, Charles
AU  - Lelarge, Marc
TI  - Near-minimal spanning trees : a scaling exponent in probability models
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2008
SP  - 962
EP  - 976
VL  - 44
IS  - 5
PB  - Gauthier-Villars
UR  - https://www.numdam.org/articles/10.1214/07-AIHP138/
DO  - 10.1214/07-AIHP138
LA  - en
ID  - AIHPB_2008__44_5_962_0
ER  - 
%0 Journal Article
%A Aldous, David J.
%A Bordenave, Charles
%A Lelarge, Marc
%T Near-minimal spanning trees : a scaling exponent in probability models
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2008
%P 962-976
%V 44
%N 5
%I Gauthier-Villars
%U https://www.numdam.org/articles/10.1214/07-AIHP138/
%R 10.1214/07-AIHP138
%G en
%F 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. https://www.numdam.org/articles/10.1214/07-AIHP138/

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

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

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

[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 | Zbl

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

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

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

Cited by Sources: