0$.
Bounding the probability of crossings by disjoint
$p_c$-paths by using the van den Berg-Kesten inequality~\cite{BK}
results in the geometric-decay property that
\begin{equation}
\P_\delta \left(\begin{array}{c}
\text{$D(r,3r)$ is traversed by}\\
\text{at least $k$ disjoint $p_c$-paths}\end{array}\right)
\ \le\ 3^{-\alpha k}\ .
\label{eq:geom-decay-perc}
\end{equation}
Since spatially separated events are independent,
a telescopic argument analogous to Lemma~\ref{lem:telescopic}
implies that {\bf H1} holds for critical Bernoulli percolation
in two dimensions, with exponents $\gamma_{B}(k)$ satisfying
\begin{equation}
\gamma_{B}(k)\ \ge\ \alpha k\, \ > \ 0\ ,\quad (0<\delta<\delta_o(r))\ .
\label{eq:H1-MST}
\end{equation}
Note that the probability of crossing
events for Bernoulli percolation does
not depend on the boundary conditions placed on $D(r,R)$.
The object is to bound the probability that
MST contains $k$ paths traversing an annulus
in terms of related events in critical Bernoulli percolation.
For a given locally finite connected graph $G$ embedded in the
plane, consider the {\em dual} graph $G^*$. Its vertices are the cells of
$G$ (i.e., the connected
components of the complement in $\R^2$ of the union
of the embedded edges of $G$). There is a dual edge $b^*$ joining two dual
vertices for each common edge in the boundary of the corresponding two cells.
In general, $G^{**}=G$, but note that $G^*$ can be a multigraph.
In particular, $\delta\Z^2$ can be
drawn with vertex set $\delta\Z^{2*}=
\delta\Z^2+\left(\frac{\delta}{2},\frac{\delta}{2}\right)$,
and each dual edge $b^*=\{x^*, y^*\}$ is the perpendicular bisector of
some edge $b=\{x,y\}$.
The dual of the graph $G^{F,W}_{r,R}$ contains
a single vertex $\partial B(r)^*$ dual to the cell
inside the free boundary at $r$ which plays the role
of a wired boundary for $G^{F,W*}_{r,R}$. A row of vertices
dual to the cells touching the wired-in point $\partial B(R)$
plays the role of a free boundary for the dual. The
analogous description holds for $G^{W,F*}_{r,R}$, with the roles
of the boundaries at $R$ and $r$ interchanged.
A dual bond $b^*$ is called $p$-occupied when $b$ is $p$-vacant.
In a potentially misleading but not uncommon usage,
the terms $p$-dual-path, $p$-dual-cluster, etc.\ are
taken here to mean the corresponding objects on the dual graph.
The vacant edges of MST on a graph $G$
form a random spanning tree model, which can be constructed
as MST on $G^*$ with call numbers $u_{b^*}= 1-u_b$.
The next lemma relates the crossings of
$D(r,R)$ by paths in MST to crossings of
the annulus by curves pieced together from
$p_c$-paths and $p_c$-dual paths. Define a {\em $p_c$-semipath}
to be a (oriented) curve consisting
of a $p_c$-dual path $\C^+$ and a $p_c$-path $C^-$
such that there is a pair of dual edges $b$ and $b^*$, so that
$b^*$ contains the last vertex of $\C^+$, and $b$ contains
the first vertex of $\C^-$ as an endpoint. We allow the special cases
of a $p_c$-path (i.e.\ $\C^+$ is empty) or a $p_c$-dual path
($C^-$ is empty).
We say a $p_c$-semipath traverses an annulus $D(r,R)$, if it
connects a (dual) vertex on one boundary of $D(r,R)$ with
a vertex on the other boundary. Two semipaths are {\em disjoint} if no edge
or dual edge of the one is the same or dual to an edge
or dual edge of the other.
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfysize=2in
\epsfbox{fsemipath.eps}
\caption{\footnotesize
A $p_c$ semipath consists of
a $p_c$-dual path $\C^+$ and a $p_c$-path $\C^-$
joined at a bond/dual bond pair.
}
\label{fig:semipath}
\end{center}
\end{figure}
\begin{lem} Suppose $\C_1,\dots \C_k$
are disjoint curves in a realization
of MST with mixed (free-wired or wired-free)
boundary conditions on $D(r,R)$ which traverse $D(r,R)$,
where $k\ge 2$. Then the corresponding realization
of Bernoulli percolation contains $k$ disjoint crossings
of the annulus by $p_c$-semipaths.
\label{lem:MST-perc}
\end{lem}
\begin{proof} To be specific, consider the case of free-wired
boundary conditions (the other case is analogous).
Orient the curves $\C_i$ to run from the free boundary at $r$ to
the wired boundary at $R$. If $\C_i$ is a $p_c$-path, then take
$\C_i^-=\C_i$, $\C_i^+=\emptyset$. For each $i$ such that
$\C_i$ is not a $p_c$-path, let
$b_i$ be the last edge along $\C_i$ with
$u_{b_i}\ge 1/2$. The portion of $\C_i$ between
$b_i$ and the wired boundary forms a $p_c$-path, which we take to be $\C_i^-$.
By Lemma~\ref{lem:cluster} applied to the dual tree, the two endpoints
of $b_i^*$ are joined to each other by a $p_c$-dual path,
which must pass through $\partial B(r)^*$ because it cannot cross
$\C_i$. Thus each of the sectors of the annulus cut out by
the set of $C_i$'s contains two of these $p_c$-dual paths,
which may well intersect. To obtain a
collection of disjoint $p_c$-semipaths $(\C_i^+,\C_i^-)$ ,
choose $\C_i^+$ to be the $p_c$-dual
path joining $\partial B(r)^*$ to the endpoint of
$b_i^*$ in the sector immediately counterclockwise from $\C_i$.
\end{proof}
One consequence of the lemma is that for MST on an annulus
of sufficiently large aspect ratio, the probability
of $k$ crossings
decays geometrically in $k$:
\begin{cor} Let $\alpha$ be the exponent defined for critical
Bernoulli percolation by (\ref{eq:def-alpha-MST}).
For every $s<\alpha/2$,
there exists $m$ large enough so that MST has the geometric-decay
property (\ref{eq:geom-decay}) on annuli $D(r,R=3^{2m}r)$.
\label{cor:geom-decay-MST}
\end{cor}
\begin{proof} We will show that for $r$ and $R$ as described
in the assertion,
\begin{equation}
\P_\delta\left(\begin{array}{c}
\text{$\Gamma^{F,W}_{r,R} [\Gamma^{W,F}_{r,R}]$ contains $k$ disjoint}\\
\text{traversals of $D(r,R)$}\end{array}\right)
\ \le\ \left( \frac{r}{R} \right)^{sk}\
\quad\text{for all }\ k\ge 2,\ 0\le\delta\le\delta_o(r)\ ,
\label{eq:geom-decay-MST}
\end{equation}
which clearly implies the claim.
Consider the case of free-wired boundary
conditions. By Lemma~\ref{lem:MST-perc}, there corresponds to
a given collection of at least two tree
crossings $\C_i$ ($i=1,\dots ,k$)
a disjoint collection of $p_c$-semipaths $(\C_i^+,\C_i^-)$,
joined at $b_i$. Let $n$ be the number
of crossings where either $\C_i$ is a $p_c$-semipath,
or $b_i$ lies in the inner annulus $D^{\text{in}}=D(r,3^mr)$
or else $b_i$ crosses the intermediate boundary at $3^mr$.
Then the semipaths contain $n$ $p_c$-paths traversing
the outer annulus $D^{\text{out}}=D(3^mr,3^{2m}r)$
and $k-n$ $p_c$-dual paths traversing the inner annulus.
We obtain
\begin{eqnarray}
\P_\delta \left(\begin{array}{c}
\text{$\Gamma_{r,R}^{F,W}$ contains $k$ disjoint}\\
\text{traversals of $D(r,R)$} \end{array}\right)
&\le& \sum_{n\le k}
\P_\delta\left(\begin{array}{c}
\text{$D^{\text{in}}$ is traversed by at}\\
\text{least $n$ disjoint $p_c$-paths}
\end{array}\right)\nonumber\\
&& \qquad
\times \P_\delta\left(\begin{array}{c}
\text{$D^{\text{out}}$ is traversed by at least}\\
\text{$k-n$ disjoint $p_c$-dual paths}
\end{array}\right)\nonumber\\
&\le& (k+1)\,3^{-\alpha m k}\nonumber \\
&\le& \left(\frac{r}{R}\right)^{[(\alpha/2 -1/\log{(R/r)}]\,k}\ ,
\end{eqnarray}
where we have used the independence of events in
$D^{\text{in}}$ and $D^{\text{out}}$ gained from the
decoupling boundary conditions in the first line,
inequality~(\ref{eq:def-alpha-MST}), its dual, and the
telescopic principle for Bernoulli percolation in
the second line, and $(k+1)\le e^k$ in the last line. The assertion
follows by choosing $R/r=3^{2m}$ sufficiently large.
\end{proof}
The corollary implies that $\gamma(k)\ge\frac{\alpha}{2} \,k$
for $k\ge 2$. The relation between the exponents for
MST and Bernoulli percolation can be tightened:
\begin{lem} For MST on $\delta\Z^2$,
the exponents $\gamma(k)$ satisfy
\begin{equation}
\gamma(k)\ \ge\ \min_{n\le k}
\left[\gamma_{B}(n) + \gamma_{B}(k-n)\right]\quad (k\ge 2)\ .
\end{equation}
\label{lem:MST-perc2}
\end{lem}
\begin{proof} Consider, again, MST with free-wired boundary
conditions on $D(r,R)$. Subdivide $D(r,R)$ into
$M$ annuli $D_j$ of equal aspect ratio $(R/r)^{1/M}$.
By Lemma~\ref{lem:MST-perc}, any collection
of at least two disjoint traversals $\C_i$ of $D(r,R)$ by
$\Gamma_{r,R}^{F,W}$ gives rise to a collection of disjoint traversals
by $p_c$-semipaths $(\C_i^+,\C_i^-)$. Hence each of the annuli $D_j$ is
traversed by a number $n_j$
of $p_c$-paths and at least $k-n_j$ $p_c$-dual paths, with the
possible exception of at most $k$ annuli which
meet one of the special edges $b_i$ (if $b_i$ crosses the
boundary between $D_j$ and $D_{j+1}$, we discard only $D_j$.)
Let $A_j^-$ (resp. $A_j^+$) denote the event that $D_j$ is
traversed by $n_j$ disjoint $p_c$-paths (resp., by $k-n_j$ disjoint
$p_c$-dual paths). Then, by the FKG inequalities,
\begin{equation}
\P (A_j^-\cap A_j^+)\ \le\ \P(A_j^-) \,\P(A_j^+)\ .
\label{eq:FKG}
\end{equation}
Using this after summing over the possible positions
of the $b_i$, and using the independence
of spatially separated events
as in the proof of Corollary~\ref{cor:geom-decay-MST} we obtain
\begin{eqnarray*}
\P_\delta \left(\begin{array}{c}
\text{$\Gamma_{r,R}^{F,W}$ contains $k$ disjoint}\\
\text{traversals of $D(r,R)$}\end{array}\right)
&\le& \P_\delta\left(\begin{array}{c}
\text{$D(r,R)$ is traversed by}\\
\text{at least $k$ $p_c$-semipaths} \end{array}\right)\\
&\le& M^k\, \left(\frac{r}{R}\right)^{(1-k/M)\,
\min_{n\le k}[\gamma_B(n) +\gamma_B(k-n)]}\ .
\end{eqnarray*}
Choosing $M$ sufficiently large proves the claim.
\end{proof}
\begin{cor} {\rm({\bf H1} for MST)} For all $k\ge 2$,
\begin{equation}
\gamma(k) \ge \ \alpha\,k \quad ,
\label{eq:lin-gamma-MST}
\end{equation}
where $\alpha>0$ is the exponent defined for critical Bernoulli percolation
by (\ref{eq:def-alpha-MST}). In particular,
{\bf H1} holds for MST with
\begin{equation}
\lambda(k) \ \ge \lamst(k)\ \ge \ \phi(k)\ \ge\ \frac{\alpha}{2}(k-1) \ .
\label{eq:lin-lambda-MST}
\end{equation}
\label{cor:H1-MST}
\end{cor}
\begin{proof} Just combine Lemma~\ref{lem:MST-perc2} with
(\ref{eq:H1-MST}), and with the results
of Lemmas~\ref{lem:lambda-phi} and
\ref{lem:phi-gamma}.
\end{proof}
%********************************************************************
\masubsect{Euclidean spanning tree}
The proof of {\bf H1} for EST follows the same general strategy as
the proof for MST in the previous subsection. The basic idea
is to relate the tree process to a percolation process,
in this case {\em droplet} percolation (sometimes called
{continuum} or {lily-pad} percolation). There are a few
additional difficulties, related
with the lack of self-duality, and the fact that events
in disjoint, but neighboring regions need not be independent.
As a consequence, the definition of {\em disjointness}
for dual traversals becomes more complicated, and the
relation we establish between crossing events in EST and droplet
percolation is not so tight. But let us now turn to
the details.
In the introduction, we defined EST in $\R^2$ as the minimal
spanning subtree of the complete graph on a collection of Poisson points
with density $\delta^{-2}$, with the edge length given by
Euclidean distance. In the droplet percolation model, the random objects
of interest are the connected clusters formed by discs
of a fixed radius $p\delta$ (where $p$ is a parameter)
centered on the Poisson points. By construction,
the Poisson process defines a coupling of EST to
droplet percolation with any parameter value $p>0$.
A {$p$-path} is a simple polygonal curve whose straight
line segments join Poisson points with distance
less than $2p\delta$. A {\em $p$-cluster} is a maximal
set of points that can be joined by
$p$-paths. As in the case of Bernoulli percolation,
there is a critical value $p_c$ for the parameter.
It follows from the results
of~\cite{Alex-RSW} (see in particular the proof of Theorem 3.4 and
Corollary 3.5 there) that
for annuli of some fixed aspect ratio $\sigma$,
\begin{equation}
\P_\delta \left( \begin{array}{c}
\text{ $D(r,\sigma r)$ is traversed}\\
\text{by a $p_c$-path} \end{array} \right)\ \le\
\sigma^{-\alpha} \quad (0<\delta\le\delta_o(r))\ ,
\label{eq:def-alpha-EST}
\end{equation}
with some $\alpha>0$. Two $p$-paths or two paths in EST are regarded
as {\em disjoint}, if they share none of their Poisson points.
With this notion of disjointness, a van den
Berg-Kesten inequality
holds for the probability of multiple disjoint $p$-crossings,
and we obtain as in the case of Bernoulli percolation
the geometric-decay property
\begin{equation}
\P_\delta \left(\begin{array}{c}
\text{$D(r,\sigma r)$ is traversed by}\\
\text{at least $k$ disjoint $p_c$-paths}\end{array}\right)
\ \le\ \sigma^{-\alpha k}\ .
\label{eq:geom-decay-droplet}
\end{equation}
A telescopic argument as in Lemma~\ref{lem:telescopic}
implies that {\bf H1} holds for droplet percolation
in $\R^2$, with exponents $\gamma_{D}(k) \ge \alpha k$.
One notable difference to Bernoulli percolation is that
droplet percolation is not self-dual. A $p$-dual cluster
is a vacant space inside which a
disc of radius $p\delta$ can be moved without
touching any Poisson points. A $p$-vacant curve is a simple
curve which keeps a distance of at least $p\delta$ to all Poisson points.
The results of \cite{Alex-RSW} imply that
\begin{equation}
\P_\delta \left( \begin{array}{c}
\text{ $D(r,\sigma r)$ is traversed}\\
\text{by a $p_c$-vacant curve} \end{array} \right)\ \le\
\sigma^{-\alpha^*} \quad (0<\delta\le\delta_o(r))\ ,
\label{eq:def-alpha*-EST}
\end{equation}
with some $\alpha^*>0$. (We have chosen $\sigma$ large
enough so that the same $\sigma$ may be used
in (\ref{eq:def-alpha-EST}) and (\ref{eq:def-alpha*-EST}).) From
this, a geometric-decay property
can be obtained for multiple crossing events ---
if a van den Berg-Kesten inequality is available.
In order to extend the van den Berg-Kesten inequality
from Bernoulli random variables to the present context,
we define a very strict notion of disjointness:
Two $p$-vacant curves are {\em spatially separated}, if
their $p\delta$-neighborhoods are disjoint, i.e., if any pair of
points on the two curves has distance at least $2p\delta$.
Then
\begin{equation}
\P_\delta \left(\begin{array}{c}
\text{$D(r,\sigma r)$ is traversed by at least}\\
\text{$k$ spatially separated $p_c$-vacant curves}\end{array}\right)
\ \le\ \sigma^{-\alpha^* k}\ .
\label{eq:geom-decay-vacant}
\end{equation}
so that ${\bf H1}$ holds for vacant percolation
with exponents $\gamma_{D}^*(k)\ge k\alpha^*$,
whose value may differ from the parameters for the droplet
percolation model itself.
As mentioned in the introduction, EST is automatically a
subgraph of the Poisson-Voronoi graph~\cite{Prep-Sha} with the natural
Euclidean edge lengths. It can be constructed with the
invasion algorithm of the previous subsection, with any vertex as
the root. An edge of the Poisson-Voronoi graph will be called
{\em p-occupied}
if it joins a pair of Poisson points of distance at most $2p\delta$,
and {\em p-vacant} otherwise. Clearly, Lemma~\ref{lem:cluster}
continues to hold for $EST$ in place of $MST$, with $\delta\Z^2$ replaced
by the Poisson-Voronoi graph of density $\delta^{-2}$ on $\R^2$,
and Bernoulli percolation replaced by droplet percolation.
For any random spanning tree model on a planar
graph $G$, we can construct a dual tree model on the dual graph $G^*$,
as explained in the previous subsection. The dual of a Poisson-Voronoi
graph in $\R^2$ can be represented with the corners of the
Poisson-Voronoi cells as dual vertices,
and the straight line segments of the cell boundaries
as dual edges. A $p$-dual path
is a simple polygonal curve consisting of the duals
of {\em p-vacant} edges in $G^*$, i.e., of boundaries of
cells defined by Poisson points that are at least a distance
$2p\delta$
apart. (See the discussion of MST for the effect of
free and wired boundaries.) Since
a $p_c$-dual path in $G^*$
is clearly a $p_c$-vacant curve, Lemma~\ref{lem:cluster} holds
also for the dual of EST and vacant percolation
(in place of MST and and Bernoulli percolation, respectively).
In accordance with the previous
definition, we define a $p_c$-semipath $(\C^+,\C^-)$
in the Poisson-Voronoi graph of density $\delta^{-2}$
to be a (oriented) curve consisting
of a $p_c$-dual path in $G^*$,
and a $p_c$-path $\C^-$ in $G$ such that
the last dual vertex of $\C^+$
lies in the boundary of the cell containing the first
vertex of $\C^-$. (We allow the same special cases
as before.) Tightening the previous definition,
we say that two $p_c$-semipaths are {\em disjoint}
if they share no vertices or dual vertices.
Then Lemma~\ref{lem:MST-perc}
continues to hold for EST in place of MST.
Although a $p_c$-dual path in $G^*$ always defines a
$p_c$-vacant curve in the plane, and conversely,
a $p_c$-vacant curve can be deformed to run
along the boundaries of Voronoi cells, the notions of
disjointness (of $p_c$-dual paths in $G^*$)
and of spatial separation (of $p_c$-vacant curves in the plane)
are different, and our proof of
Corollary~\ref{cor:geom-decay-MST} has to be changed
accordingly:
\begin{cor} Let $\alpha$, $\alpha^*$, and $\sigma$
be the parameters defined for droplet and vacant
percolation in (\ref{eq:def-alpha-EST}) and
(\ref{eq:def-alpha*-EST}). For $s\le \min(\alpha,\alpha^*)/4$,
EST has the geometric-decay property (\ref{eq:geom-decay})
on annuli $D(r,R=\sigma^{2m}r)$ with a sufficiently large integer $m$.
\label{cor:geom-decay-EST}
\end{cor}
\begin{proof} We will show that, for $r$ and $R$ as in the statement,
\begin{equation}
\P_\delta \left(\begin{array}{c}
\text{$\Gamma_{r,R}^{F,W}[\Gamma^{W,F}_{r,R}]$ contains $k$ disjoint} \\
\text{traversals of $D(r,R)$}
\end{array}\right)
\ \le\ \left(\frac{r}{R}\right)^{2s\lfloor k/2 \rfloor }
\quad \text{for all}\ k\ge 2,\ 0<\delta\le\delta_o(r)\ .
\end{equation}
Subdivide $D(r,R)$ into
an inner annulus $D^{\text{in}}=D(r,\sigma^mr)$ and an outer annulus
$D^{\text{out}}=D(\sigma^mr,\sigma^{2m}r)$, and consider
the disjoint semipaths
$(\C_i^+,\C_i^-)$ corresponding to the $k$ traversals of
the annulus by the tree. As in the proof of
Corollary~\ref{cor:geom-decay-MST}, we obtain
$n$ crossings of $D^{\text{out}}$
by $p_c$-paths $\C_i^-$ in the Poisson-Voronoi graph,
and $k-n$ crossings $D^{\text{in}}$ by $p_c$-dual paths $\C_i^+$.
By definition, each $\C_i^-$ is a $p_c$-path for droplet
percolation, and disjoint $p_c$-semipaths lead to disjoint
$p_c$-paths. Similarly, each of the paths $\C_i^+$
along the edges in $G^*$
can be parametrized as a curve in the plane that
keeps distance at least $p_c\delta$ from all Poisson points.
The complication here is that the $p_c$-vacant
curves $\C_i^+$ need not be spatially separated according to our
definition given above even for disjoint semipaths.
However, by Lemma~\ref{lem:vacant-separated} proved below,
we can use the way the $\C_i^+$ are confined to the sectors
cut out of $D(r,R)$ by the set
of $\C_i$'s, to find at least $\lfloor (k-n)/2\rfloor$ $p_c$-vacant paths
among the $\C_i^+$'s which are spatially separated, except possibly,
for their first and last edges. (As usual, the possibility of
long edges introduces a correction which is exponentially small
in $\delta^{-2}$.)
The proof is completed by using the
independence of events in $D^{\text{in}}$ and $D^{\text{out}}$
(with the decoupling boundary conditions), and
the geometric decay properties (\ref{eq:geom-decay-droplet})
and (\ref{eq:geom-decay-vacant}) for droplet and vacant percolation.
\end{proof}
\begin{lem} Let $b=\{x,y\}$ be an edge of
EST with density $\delta^{-2}$, and let $P$ be a $p_c$-dual path
in $G^*$ (the dual of the corresponding Poisson-Voronoi graph)
with $p_c$ the critical parameter value for
droplet percolation. Assume that no edge of
$P$ is dual to $b$. Then the distance between $b$
and all non-terminal segments of $P$ is at least $p_c\delta/2$.
\label{lem:vacant-separated}
\end{lem}
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfysize=1in
\epsfbox{ftriangle.eps}
\caption{\footnotesize
Two possible positions of an edge $b=\{x,y\}$ in the Poisson-Voronoi
graph relative to a $p_c$-dual path $P$ containing the
boundaries of the Voronoi cells of $x$ and $y$. The cells of
$x$ and $y$ meet the cell of $w$ at $z^*$, which is point
on $P$ closest to $b$.
}
\label{fig:triangle}
\end{center}
\end{figure}
\begin{proof} The minimal
distance between $b$ and the non-terminal segments of $P$ is
realized
for a pair of points involving either an endpoint of
$b$ or the endpoint of a segment of $P$. In the first case, we are
done, since $P$ has distance at least $p_c\delta$ from
any Poisson point, and in particular from the vertices
$x$ and $y$. In the second case, the minimal distance is assumed
somewhere between a point on $b$ and a vertex $z^*$ of $G^*$
on $P$. We need to find a lower bound for the height
$h$ of the triangle $xyz^*$. Assume, without loss of generality,
that $z^*$ lies on the common boundary of the
Voronoi cells of $x$ and $y$ with the cell of another point $w$ (otherwise,
the tree contains an edge that is closer to $z^*$ than $b$).
In other words, $z^*$ is the center of the circle
through $x$, $y$, and $w$.
Both $\{x,w\}$ and $\{y,w\}$ have
length at least $2p_c\delta$, because $P$ contains their duals.
Moreover, one of them (say $\{x,w\}$) is longer than $b$,
because EST contains $b$. If the triangle $xyw$ has an obtuse angle
at $y$, then $\{x,w\}$ has length
at least $\sqrt{4(p_c\delta)^2+\ell^2}$ (where $\ell$ is the length of $b$),
so that the distance of $z^*$ to both $x$ and $y$ exceeds half of that value.
Since $z^*$ lies on the perpendicular bisector of $b$,
we see with the Pythagorean theorem that $h\ge p_c\delta$.
If the triangle $xyw$ has acute angles at both $x$ and $y$,
we slide $x$ and $y$ apart in such a way that the line through
$x$ and $y$ and their perpendicular bisector
are preserved, until the lengths of $\{x,y\}$ and $\{x,w\}$
coincide. While this increases the lengths of all sides
of the triangle $xyw$, it can only decrease $h$,
since the intersection of the Voronoi cells of $x$ and $y$ with
the bisector
of $b$ shrinks. Elementary geometric considerations show that
$h^*$ exceeds $p_c \delta /2$ (see Figure~\ref{fig:triangle}).
\end{proof}
Lemma~\ref{lem:MST-perc2} and Corollary~\ref{cor:H1-MST}
have to be modified as well:
\begin{lem} In the case of EST of density $\delta^{-2}$ on $\R^2$,
the exponents $\gamma(k)$ satisfy
\begin{equation}
\gamma(k)\ \ge\ \min_{n\le k}
\left[\gamma_D(n) + \gamma_D^*(\lfloor (k-n)/2\rfloor )\right]
\quad (k\ge 2)\ .
\end{equation}
\label{lem:EST-perc2}
\end{lem}
\begin{cor} {\rm({\bf H1} for EST)} For all $k\ge 2$,
\begin{equation}
\gamma(k) \ge \ \min(\alpha,\alpha^*)\,
\left\lfloor \frac{k}{2}\right\rfloor \quad ,
\label{eq:lin-gamma-EST}
\end{equation}
with $\alpha, \alpha^*>0$ as defined above. In particular,
{\bf H1} holds for EST with
\begin{equation}
\lambda(k) \ \ge \lamst(k)\ \ge \ \phi(k)\ \ge\ \min(\alpha,\alpha^*)\,
\left\lceil\frac{k-1}{4}\right\rceil\quad .
\label{eq:lin-lambda-EST}
\end{equation}
\label{cor:H1-EST}
\end{cor}
\begin{proof} Combine Lemma~\ref{lem:EST-perc2} with
the general inequalities between the exponents of
Lemmas~\ref{lem:lambda-phi} and \ref{lem:phi-gamma}.
\end{proof}
\remark In Corollary~\ref{cor:H1-EST} and
Lemma~\ref{lem:EST-perc2}, the expression $\lfloor (k-n)/2\rfloor$
can be replaced by $1$ when $k-n=1$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%new section
\masect{Verification of {\bf H2} }
\label{sect:rough}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We shall now verify the roughness criterion. In contrast
with the
previous section, our arguments here will rely mostly
on the tree structure, symmetry, and planarity. In particular,
the result of this section also applies to the
uniform spanning tree on the
Poisson-Voronoi graph. The main idea is seen
in the following lemma.
\begin{lem}
Let $\Gamma(\omega)$ be a random tree model on $\R^2$, and let $B$
be a rectangle in the plane. Suppose that the distribution of
the model is symmetric under a group of
transformations in the plane which is large enough
so that some collection $B_1,\dots ,B_n$ of images of $B$ under
these transformations can be positioned in such a way that any
collection of $n$ curves $\C_i$ traversing $B_i$
($i=1,\dots , n)$ forms a loop.
Then
\begin{equation}
\P\left(
\begin{array}{c}
\text{ $B$ is traversed (in the long } \\
\text{ direction) by a path in $\Gamma$ }
\end{array}
\right) \ \le \ 1 - \frac{1}{n} \; .
\label{eq:h2event}
\end{equation}
\label{lem:h2event}
\end{lem}
\remark If the model has the symmetries of the
square lattice, $B$ can be any sufficiently long rectangle, and
$B_i$
($i=1,\dots ,4$) are the images of $B$ under rotation by $\pi/2$
about a sufficiently close lattice point. For the hexagonal and
triangular lattice, we would use rotations by $2\pi/3$
in the same way.
\begin{proof}
Since the random tree contains no loops, the probability
that all $B_i$ are traversed simultaneously must vanish.
Thus, with probability one at least one of the $B_i$
fails to be traversed. By our symmetry assumption,
the probability of failure has to be at least
$1/n$, which proves \eq{eq:h2event}.
\end{proof}
The above observation will now be supplemented by a decoupling
argument.
\begin{lem} Let $\Gamma_\delta(\omega)$
be one of the four spanning tree models on $\R^2$ described in the
introduction, with cutoff parameter $\delta$, and let
$\{ A_1,\ldots,A_k \}$ be a collection of well separated rectangles
of common aspect ratio (length/width) $\sigma > 2$. Then
\begin{equation}
\limsup_{\delta \to 0} \ \P_\delta\left( \begin{array}{c}
\text{each $A_j$ is traversed (``lengthwise'') } \\
\text{by a curve in $\F_{\delta}^{(2)}(\omega)$ }
\end{array}
\right)\ \le\ \rho^k \;
\end{equation}
with $\rho = 3/4$. Furthermore, with some other values of
$\rho < 1$, and $\sigma < \infty$, the above bound on the probability
applies for all $\delta < \min_j \ell_j$ (i.e.,
also the full hypothesis {\bf H2} holds).
\label{lem:H2}
\end{lem}
\begin{proof} \
Let us consider first the case of the spanning trees on $\delta \Z^2$.
For each of the $A_j$, we pick a lattice point $x_j$
outside $A_j$, but as close as possible to the midpoint
of one of the long sides. Let $\Lambda_i$ be
the disc of radius $\sigma \ell_j$ about $x_j$.
Then $\Lambda_j$ contains $A_j$. The discs are disjoint
since the separation between
$A_j$ and the other rectangles is larger
than $2\sigma\ell_j$.
Introducing free boundary conditions on the
$\Lambda_j$ will only enhance
the crossing probabilities, while decoupling the crossing events
in disjoint discs. We next check the assumptions
of Lemma~\ref{lem:h2event}. Clearly, in each
of $\Lambda_j$ the tree processes
(with free boundary conditions)
is symmetric under rotation by $\pi/4$ about $x_j$.
If $\delta$ is small enough
($ \delta \le \frac{\sigma-2}{4\sqrt{2}}
\,\min{\ell_j}$ will do), then the images
of $A_j$ under the four rotations by
multiples of $\pi/2$ intersect in such a way that
any simultaneous crossings would form a loop.
By Lemma~\ref{lem:h2event} the crossing probabilities
are independenty bounded by $3/4$. This implies both claims for
the UST and the MST.
An additional consideration is needed for the models
on the Poisson-Voronoi graph. One may
take here $\sigma=2$, choose $x_j$ to be the midpoint of
a long side of $A_j$, and let $\Lambda_j$ be the disc of
radius $\sigma\ell_j$ about $x_j$.
The
the probability that each $A_j$ is crossed by the
restriction of the tree to $\Lambda_j$ is bounded by $(3/4)^k$,
by the same argument as above. However, a small
correction has to be added to allow for the possibility
of an edge crossing $A_j$ and the boundary of $\Lambda_j$.
As discussed in Section~\ref{sect:crossing}, the probability
of such a long edge can be dominated by
$B e^{-A(\sigma \ell_j/\delta)^2}$, with suitable constants
$0 < A,\ B < \infty$. The claim then easily follows
also for that case.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\masect{Conclusion}
\label{sect:conclusion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The scale invariant bounds derived in Sections~\ref{sect:reg}
and~\ref{sect:rough} will now be used to prove
the two Theorems stated in the Introduction.
%****************************************************
\masubsect{Tightness, regularity, and roughness}
\label{subsect:limit}
The basic strategy for the proof of Theorem~\ref{thm:main1}
is to apply the regularity and roughness
results for random curves
(Theorems~\ref{thm:reg-curves} and~\ref{thm:rough-curves},
see Section~\ref{sect:criteria})
to the branches of the random trees to obtain the
tightness of the family $\{\mu_\delta^{(2)}\}$, and then use
the structure of the spaces $\Om^{(N)}$ and $\Om$
to obtain tightness of $\{\mu_\delta^{(N)}\}$ and $\mu_\delta$.
The statement about the locality and basic structure
follows from the positivity of $\lambda(2)$.
\bigskip
\begin{proof_of}{Theorem~\ref{thm:main1}} \
\medskip
{\em Existence of limit points:} We verified that
$\F^{(2)}_\delta$ satisfies the regularity criterion {\bf H1}
in $\R^2$
for each of the systems of curves along UST, MST, and EST
(Corollaries~\ref{cor:H1-UST}, \ref{cor:H1-MST}, and~\ref{cor:H1-EST},
respectively). By Lemma~\ref{lem:H1-sphere}, the corresponding
bound on crossing probabilities
holds (with the same exponents) also for the
system on $\sp^2$ with the metric $d(x,y)$ given by
(\ref{eq:def-metric}).
Theorem~\ref{thm:reg-curves} implies that
the family of measures $\mu^{(2)}_\delta$ is tight, and
that subsequential scaling limits exist for the system of random
curves $\F^{(2)}$.
Since for $N>2$ the spaces $\S^{(N)}$, constructed
by patching together spaces $S^{\tau}$, are closed
subspaces of $\left[\S^{(2)}\right]^{2N-3}$ (see the
discussion at the end of Subsection~\ref{sect:graphs}.a),
the family of measures $\mu_\delta^{(N)}$ on $\Om^{(N)}$
is tight also for each $N>2$. (There is nothing to show for $N=1$.)
Tightness of the measures $\mu_\delta$
on the product space $\Om\subset{\sf X}_{N\ge 1} \Om^{(N)}$
now easily follows by an application of Tychonoff's theorem.
\medskip
The tightness described above
guarantees the existence of a sequence $\delta_n \to 0$ for which
the limit $\lim_{n\to \infty}\mu_{\delta_n}(\cdot)$
exists in the sense of weak convergence of measures on
${\sf X}_{N\ge 1} \Om^{(N)}$, as described
by \eq{eq:weakconvergence}.
%As explained there, this compactness argument does not yet permit
% us to
%deduce that the tree collections $\F$ typical for the limiting
%measure represent single spanning
%trees in $\R^2$ (according to Definition~\ref{df:inclusive}.
%All we can say at this stage
%is that $\F^{(1)}=\dot \R^2$ and that the trees of $\F$ offer a good
%approximation to those trees of $\F_{\delta}$ which do not
%stretch ``too far out'',
%i.e.\ to infinity as $n\to \infty$.
To see that a limiting configuration typically describes
a single spanning tree in $\R^2$, we use
that the exponent $\lambda(2)$ is positive
by Corollaries~\ref{cor:H1-UST}, \ref{cor:H1-MST},
and~\ref{cor:H1-EST}.
For $r>0$ and $\delta>0$,
define the random variable $R_{\delta;r}(\omega)$
to be the radius of the smallest ball containing
all trees with endpoints in $B(r)$ , and let $R_r(\omega)$
be the corresponding variable in a scaling limit.
Condition {\bf H1} says that
\begin{equation}
\P_\delta \left( \frac{R_{\delta;r}(\omega)}{r}\ \ge\ u\right)\ \le \
K(2,s) u^{-(\lambda(2)-s)}\ ,
\label{eq:quasilocal}
\end{equation}
so that $\F_\delta$ is {\em uniformly quasilocal}
in the sense that $R_{\delta;r}$ is stochastically bounded
as $\delta\to 0$. Moreover, (\ref{eq:quasilocal})
also holds for $R_{r}(\omega)$ for any scaling limit of
the system.
In particular, $\mu$-almost every limiting configuration
$\F(\omega)$ is quasilocal, and represents a single tree spanning $\R^2$.
\medskip{\em Regularity:}
Theorem~\ref{thm:reg-curves} guarantees furthermore
that for every $\alpha<1/2$,
the curves in the limiting object $\F(\omega)$
can be parametrized, by functions $g(t)$ which
are H\"older continuous (using the metric given by
(\ref{eq:def-metric})
on $\sp^2$), with exponent $\alpha$
and a random prefactor whose distribution depends on $\alpha$,
that is,
\begin{equation}
d(g(t), g(t'))\ \le\ K_{\alpha}(\omega)
|t-t'|^\alpha\ \qquad 0\le t, t'\le 1 \; .
\label{eq:holder-sphere}
\end{equation}
Rewriting equation~(\ref{eq:holder-sphere}) in terms of
the original metric on $\R^2$, we obtain
\begin{equation}
|g(t)- g(t')| \ \le \ K_{\alpha}(\omega) \,
(1+|g(t)|^2 + |g(t')|^2)\, |t-t'|^\alpha \; .
\end{equation}
The last conclusion from Theorem~\ref{thm:reg-curves}
is that in $\mu$-almost all configurations of any scaling
limit, all the curves have Hausdorff dimension at
most $2-\lambda(2)$.
\medskip{\em Roughness:}
Since $\F^{(2)}_{\delta}$
also satisfies the roughness criterion {\bf H2$^*$}
by Lemma~\ref{lem:H2}, Theorem~\ref{thm:rough-curves} implies
that the limiting measure $\mu^{(2)}$ is
supported on collections containing
only curves whose Hausdorff dimension is bounded below by
some $d_{\min}>1$, which depends on the parameters
in {\bf H2$^*$}. In particular, curves in scaling
limits cannot be
parametrized H\"older continuously with any exponent $\alpha>d_{\min}^{-1}$.
This concludes the proof of the convergence, regularity, and
roughness assertions of Theorem~\ref{thm:main1}.
\end{proof_of}
%**********************************
\masubsect{Properties of scaling limits}
The main tool for the proof of Theorem~\ref{thm:main2} is
the fact that the limiting measure inherits the power
bounds associated with the exponents $\lamst(k)$,
as explained in Theorem~\ref{thm:semicontinuity}.
It is convenient to employ here the following
notion of degree, which classifies the local behavior
of a collection of trees near a given point $x \in \R^2$.
\begin{df} The \underline{degree}
of an immersed
tree at a point $x$ is given by
\begin{equation}
\deg_T(x)\ =\ \sum_{\xi:f(\xi)=x} \deg_\tau(\xi)\ ,
\end{equation}
where $f:\tau\to\R^2$ is a parametrization of $T$ which
is non-constant on every link.
Here $ \deg_\tau(\xi) $ is the branching number of the reference
tree $\tau$ at $\xi$ if $\xi$ is a vertex of $\tau$, and it is
taken to be $2$ if $\xi$ lies on a link of $\tau$.
For a collection of trees $\F$ immersed in $\R^d$, the degree
at $x$ is
\begin{equation}
\deg_{\F}(x) \ = \ \sup_N \sup_{T\in\F^{(N)}}\ \deg_T(x)\ .
\end{equation}
\label{df:degree}
\end{df}
A more refined notion is that of the \underline{degree-type} of
$T$ at $x$, which is
the multiset of the summands in the above definition of degree. The
notions in Definition~\ref{df:point} can be expressed in terms of
degree-type. For instance, a point of uniqueness
is one whose degree-type has one part for every tree $T$ in $\F$.
A branching point is one with degree-type (for some $T$ in $\F$)
containing a part that is at least 3, and a pinching point is one with
two parts at least 2.
%% A more refined notion is that of the {\underline degree-type} of
%% $T$ at $x$ $\operatorname{type}_T(x)$, which is
%% the multiset of the summands in the above definition of degree.
%% As above, the degree type of $x$ is
%% \begin{equation}
%% \operatorname{type}_{\F}(x) \ = \ \sup_N \sup_{T\in\F^{(N)}}\
%% \operatorname{type}_T(x)
%% \end{equation}
%% (where the supremum is with respect to the partial order $a\leq b$
%% when $a$ is a subset of a refinement of $b$).
%% The
%% notions in Definition~\ref{df:point} can be expressed in terms of
%% degree-type. For instance, a point of uniqueness
%% is one whose degree-type has one part.
%% A branching point is one with degree-type
%% containing a part that is at least 3, and a pinching point is
%% one with two parts at least 2.
One may note that $\deg_{\F}(x) = 1$ implies that $x$ is a point
of uniqueness. Such points are also points of continuity,
in the sense seen in the following statement.
\begin{lem} If $\F$ is a closed inclusive collection
of trees representing a single spanning tree in $\R^d$,
and $\eta=\{x_1, \ldots , x_N \} $ is an $N$-tuple
consisting of distinct points of uniqueness, then
$\F$ includes exactly one subtree, denoted $T^{(N)}(\eta)$,
with the set of external vertices given by $\eta$.
Moreover, if the external vertices of a sequence of
trees $\{T_n\}$ in $\S^{(N)}$
satisfy
\begin{equation}
\eta_n \too{n\to\infty} \eta
\label{eq:eta}
\end{equation}
in $\left(\R^d\right)^N$, then
\begin{equation}
T_n \too{n\to\infty} T^{(N)}(\eta)\
\end{equation}
with respect to the metric on $\S^{(N)}$.
\label{lem:unique}
\end{lem}
\begin{proof}
Assume that $\F$ contains two trees, $T_1$ and $T_2$
with external vertices given by $\eta$. Since $\F$ represents a single
spanning tree, there exists a tree $T$ (parametrized as $f:\tau\to\R^d$)
containing both $T_1$ and $T_2$, with no external vertices
beyond $\eta$. If $T_1\not = T_2$, then at least one of the
two trees (say $T_1$) is parametrized under $f$ by a proper subset
$\tau_1$ of $\tau$. Let $\xi$ be an external vertex
of $\tau$ not contained in $\tau_1$; clearly $x=f(\xi)$ is one
of the points $x_1,\dots ,x_N$ in $\eta$. By assumption,
there exists a point $\tilde\xi$ in $\tau_1$ with
$f(\tilde\xi)=x$. Since $\F$ is inclusive, it contains
the curve obtained by joining $\xi$ to $\tilde\xi$
in $\tau$ and applying $f$. This is the desired curve
which starts and ends at $x$.
To see the continuity statement, note that the closedness
of $\F$ implies that any limit of a sequence of trees whose
external vertices satisfy the
assumption (\ref{eq:eta}) is certainly contained in $\F$,
and has external vertices $\eta$. The uniqueness result implies the
claim.
\end{proof}
The dimension of the set of the points of
degree $k$ can be estimated in terms of the exponents
$\lamst(k)$.
\begin{lem} Let $\mu(d\F)$ be a probability measure on $\Om$
describing a random collection of trees in $\R^d$, and assume
it satisfies the
power-bound (\ref{eq:lambda-bar}), on the probability of
multiple disjoint crossings of annuli, with a family of
exponents $\lamst(k)$.
For each realization $\F$, let
\begin{equation}
A_k(\F)\ =\ \left\{ x\in\R^d\ \mid\ \deg_{\F}(x)\ge
k\right\} \; .
\end{equation}
Then:
\begin{itemize}
\item[i.]
For $\mu$-almost every $\F$ the Hausdorff dimensions of
$A_k(\F)$ satisfy
\begin{equation}
\dim_{\mathcal H}A_k(\F) \ \le \ \left( d-\lamst(k) \right)_+ \; ,
\end{equation}
in particular
\begin{equation}
\lamst(k) > 0 \Longrightarrow A_k(\F) \
\mbox{is of zero Lebesgue
measure} \; ;
\end{equation}
\item[ii.]
\bea
\lamst(k)>d & \Longrightarrow & A_k(\F)=\emptyset \
\mbox{for $\mu$-almost every $\F$, i.e.,} \\
& & \quad
\sup_{x\in \R^d} \ \deg_{\F}(x) \ < \ k,\
\mbox{$\mu$-almost surely} \nonumber \; .
\eea
\end{itemize}
\label{lem:dim}
\end{lem}
\begin{proof} For $R>0$, we denote by $A_{k,R}(\F)$
the set of all points $x\in \R^{d}$ such
that for all $r \in (0,R)$ the tree configuration $\F$
exhibits at least $k$
microscopically disjoint traversals of $D(x,r,R)$.
The definition of the degree implies
\begin{equation}
A_k(\F)\ \subset \ \bigcup_{1\ge R>0} A_{k,R}(\F)\ \; ,
\end{equation}
where it suffices to take $R=2^{-j}$, $j=1,2,\ldots$.
By translation invariance (of $\lamst(k)$ and $\dim_{\mathcal H}$),
and the fact that
the Hausdorff dimension of a countable union
of sets of dimension $\le \nu$ does not exceed $\nu$,
it suffices to show that for any given $R<1$
\begin{equation}
\dim_{\mathcal H}A_{k,R}(\F)\cap [0,1]^d
\ \le \ d-\lamst(k) \ .
\label{eq:dimension}
\end{equation}
Let now $N(k,r,R;\F)$ be the number of balls of radius
$r$ needed to cover $A_{k,R}(\F)\cap [0,1]^d$.
Covering the unit square by $\c r^{-d}$ balls of radius $r$,
we see that for any $s<\lamst(k)$,
the expectation value satisfies
\begin{equation}
\E\left( N(k,r,R;\F) \right) \le \c(R,s)\,r^{s-d} \; .
\label{eq:hausdorff}
\end{equation}
By Chebysheff's inequality, the random variables
$r^{d-s} N(k,r,R)$ are stochastically bounded
uniformly in $r$. Equation (\ref{eq:dimension})
readily follows.
In case $d-\lamst(k) < 0$,
the above covering argument implies that the set is almost
surely empty.
\end{proof}
We shall now use the above observations to complete the proof
of the second set of results stated in the introduction.
\medskip
\newpage % to avoid a bad break
\begin{proof_of}{Theorem~\ref{thm:main2}} \
{\em Singly connected to infinity:}
Let $\F(\omega)$ be a scaling limit
of one of the three random tree
models considered here (UST, MST, or EST). Note that
if $\F$ was not singly connected to infinity, then,
with positive probability, it would contain two microscopically
disjoint paths traversing annuli $D(r,R)$ with arbitrary large
aspect ratio. This contradicts the strict positivity of
$\lamst(2)$.
\medskip{\em Points of uniqueness and exceptional points:}
Points of degree one are automatically points of uniqueness.
Thus, the claim that Lebesgue-almost all points are
points of uniqueness is implied by the condition
$\lamst(2) > 0$, through Lemma~\ref{lem:dim}
with $k=2$. This also shows that the set of
exceptional points has dimension less than two.
To see that exceptional points are
dense, it is instructive to consider the dual model, which
in two dimensions is also a spanning tree.
Any interior point of a curve in a
scaling limit of the dual tree model is a point of
non-uniqueness for the original spanning tree.
In two dimensions, the exponents $\gamma(k)$ are shared by
the model and its dual for all the models discussed here
(because the graph $G_{r,R}^{F,W}$ is dual to $(G^*)^{W,F}_{r,R}$),
even in the absence of the self-duality exhibited by UST and MST
so that the dual models also
satisfies the hypothesis {\bf H1} and {\bf H2$^*$}.
That makes the roughness assertion (\ref{eq:dmin}) of
Theorem~\ref{thm:main1} applicable also to the
dual models, and hence almost surely the dimension
of each dual curve is strictly larger than one.
Also, since a scaling limit of the dual model is
a single spanning tree, the set of interior
points of its curves is clearly dense in $\R^2$.
\medskip
{\em Countable number of branching points:}
In order to establish that the collection of
branching points is countable, it suffices to
show that for every $\eps>0$ there are only countably many
points at which branching occurs with three or more branches
extending to a distance greater that $2\eps$. (The collection
of branching points is a countable union of
such sets, with $\eps=2^{-n}$.) We shall refer to such
points as {\em branching points of scale $\eps$}. As a further
reduction,
we note that it suffices to prove that in any finite region,
there are typically only finitely many such points. Thus,
the countability is implied by part (i) of
the following claim.
\begin{quotation}
\noindent {\bf Claim:} {\em
Let $N_\eps (\F)$ be the number of points of branching
of scale $\eps$, within the unit cell $\Lambda = [0,1]^2$. Then
\begin{itemize}
\item[i.] $\mu(d\F)$ - almost surely
\begin{equation}
N_\eps (\F) \ < \ \infty \; ,
\end{equation}
\item[ii.] for each integer $k$ such that
$\lamst(k) > 2 \ (=d)$
\begin{equation}
\P\left( N_{\eps} \ge m \right) \ \le \
\frac{\c(k)}{\eps^{\lamst(k)} } \
\left( \frac{k}{m} \right)^{ \frac{\lamst(k) - 2}{2} } \; ,
\label{eq:rational}
\end{equation}
for all $m\ge k/\eps^{2}$ (where $\P$
is with respect to the measure $\mu$).
\end{itemize}
}
\end{quotation}
\begin{proof_claim}\
Part (i) is of course implied by (ii). To prove (ii),
let us partition the unit square into
square cells of diameter $r\le \eps$,
with $r$ determined by
\begin{equation}
m \ = \ k / r^{2} \; .
\end{equation}
This choice of $r$ guarantees that
if $N_\eps (\F) \ge m$ then in at least one of the cells
$\F$ has $k$, or more, branching points of scale $\eps$.
Now, if a given cell contains $k$ such points, then $\F$ includes
a subtree which within this cell has $k$ branching points, with all
branches extending further than $2\eps-r\ge\eps$ from the cell's center.
This implies that the annulus concentric with the cell, with
inner radius $r$ and outer radius $\eps$, is traversed by at least
$k+2$ microscopically disjoint curves.
(This topological fact was employed in a vaguely related
context by Burton and Keane~\cite{BuKe}.)
Adding our bounds for
the probabilities for such events
($\c(k) (r/ \eps)^{\lamst(k)}$ for each cell), we get
\begin{equation}
\P\left( N_{\eps} \ge m \right) \ \le \
\frac{1}{r^{2} } \ \c(k) \
\left(\frac{ r}{\eps}\right)^{\lamst(k)} \; ,
\end{equation}
which leads directly to \eq{eq:rational}.
\end{proof_claim}
\medskip
{\em Non-random bound on the degree of branching points:}
The absence of branching points of arbitrary high degree
is a direct consequence of $\lamst(k)\to\infty \ (k\to\infty)$
by Lemma~\ref{lem:dim} (ii).
\end{proof_of}
\noindent{\bf Remark: } We conjecture that the maximal
branching number is actually $k=3$. From the perspective
of this work this is suggested by the
countability of the branching points, which may be an
indication that
$\lamst(3) = 2 \ (=d)$.
If $\lamst(k)$ is also strictly monotone
in $k$, then $\lamst(4) > 2 \ (=d)$ and the suggested
statement then follows by Lemma~\ref{lem:dim} (ii).
However, neither of the two steps in this argument
has been proven. We note that both are consistent with
the exact predictions for UST, viewed as the $Q\to 0$ limit
of critical Potts models~\cite{Nienhuis,DS}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\startappendix
\vspace{1truecm plus 1cm}
\noindent {\Large\bf Appendix}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%new section
\maappendix{Quadratic growth of crossing exponents}
\label{sect:quad}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In Section~\ref{sect:reg} it was established that
the crossing exponents $\gamma(k)$
for UST, MST, and EST, grow at least
linearly with $k$, as $k\to\infty$.
We shall now prove that the
growth is even faster: quadratic in $k$.
Our derivation extends the analysis of
ref.~\cite{AizISC} where a similar statement was proved for
independent percolation in $d=2$ dimensions.
It was also suggested there (but not proved)
that the proper generalization, for
dimensions $d$ where $\gamma(k)$ does not vanish, should
be $ \gamma \asymp k^{d/(d-1)}$.
The improved argument presented here yields such a
lower bound for all dimensions $d\ge 2$.
\noindent {\bf Remark: }
It has been proposed for a number of related problems in two
dimensions that exponents similar to $\gamma(k)$ are given {\it
exactly\/} by a quadratic polynomial in $k$~\cite{Nienhuis,DS}. In
particular, the prediction for UST (viewed as the $Q=0$ critical
Potts model) is $(k^2-1)/4$. It would be of interest to see
mathematical methods capable of resolving such issues.
We start by deriving an upper bound on the exponents,
using reasoning analogous to that found in ref.~\cite{AizISC}.
\begin{lem}
The actual rate of growth of $\gamma(k)$ is not faster than order
$k^{d/(d-1)}$ for UST. In $d=2$ dimensions,
that applies also to MST and EST.
\end{lem}
\begin{proof}
We will show for each of the models that there exists a constant
$\beta<\infty$ so that for all spherical shells $D(r,R)$
(with $0