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) no. 5, pp. 962-976

Abstract (VO)

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 $\delta$ 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+\Theta \left({\delta }^2\right)$. We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.

Résumé

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 $\delta$ 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+\Theta \left({\delta }^2\right)$. 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.

Détail

DOI : 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