\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Abraham D. Flaxman}
%
%
\medskip
\noindent
%
%
{\bf The Lower Tail of the Random Minimum Spanning Tree}
%
%
\vskip 5mm
\noindent
%
%
%
%
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)$.



\bye

.