Geodesic
The lower tail of the random minimum spanning tree
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
Consider a complete graph $K_n$ where the edges have costs given by independent random variables, each distributed uniformly between 0 and 1. The cost of the minimum spanning tree in this graph is a random variable which has been the subject of much study. This note considers the large deviation probability of this random variable. Previous work has shown that the log-probability of deviation by $\varepsilon$ is $-\Omega(n)$, and that for the log-probability of $Z$ exceeding $\zeta(3)$ this bound is correct; $\log {\rm Pr}[Z \geq \zeta(3) + \varepsilon] = -\Theta(n)$. The purpose of this note is to provide a simple proof that the scaling of the lower tail is also linear, $\log {\rm Pr}[Z \leq \zeta(3) - \varepsilon] = -\Theta(n)$.
DOI : 10.37236/1004
Classification : 05C80, 60C05
Mots-clés : random variable, deviation probability, log-probability 
Abraham D. Flaxman. The lower tail of the random minimum spanning tree. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/1004
@article{10_37236_1004,
     author = {Abraham D. Flaxman},
     title = {The lower tail of the random minimum spanning tree},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/1004},
     zbl = {1113.05090},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1004/}
}
TY  - JOUR
AU  - Abraham D. Flaxman
TI  - The lower tail of the random minimum spanning tree
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1004/
DO  - 10.37236/1004
ID  - 10_37236_1004
ER  - 
%0 Journal Article
%A Abraham D. Flaxman
%T The lower tail of the random minimum spanning tree
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/1004/
%R 10.37236/1004
%F 10_37236_1004

Cité par Sources :