Annales de l’Institut Henri Poincaré - Probabilités et Statistiques
2008, Vol. 44, No. 5, 962–976
DOI: 10.1214/07-AIHP138
© Association des Publications de l’Institut Henri Poincaré, 2008
www.imstat.org/aihp
Near-minimal spanning trees: A scaling exponent
in probability models
David J. Aldousa,1, Charles Bordenaveb,2 and Marc Lelargec,3
aUniversity of California, Department of Statistics, 367 Evans Hall # 3860, Berkeley CA 94720-3860, USA. E-mail: aldous@stat.berkeley.edu
bÉcole Normale Supérieure, Département d’Informatique, 45 rue d’Ulm, 75230 Paris Cedex 5, France. E-mail: charles.bordenave@ens.fr
cINRIA-ENS, 45 rue d’Ulm, 75230 Paris Cedex 5, France. E-mail: marc.lelarge@ens.fr
Received 22 October 2006; revised 3 April 2007; accepted 1 June 2007
Abstract. 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.
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 δ 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.
MSC: 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
1. Introduction
This paper gives details of one aspect of the following broad project [1]. Freshman calculus tells us how to find
a minimum x∗ of a smooth function f (x): set the derivative f (x∗) = 0 and check f (x∗) > 0. The related series
expansion tells us, for points x near to x∗, how the distance δ = |x − x∗| relates to the difference ε = f (x) − f (x∗)
in f -values: ε scales as δ2. This scaling exponent 2 persists for functions f : Rd → R: if x∗ is a local minimum and
ε(δ) := min{f (x) − f (x∗): |x − x∗| = δ), then ε(δ) scales as δ2 for a generic smooth function f .
Combinatorial optimization, exemplified by the traveling salesman problem (TSP), is traditionally viewed as a
quite distinct subject, with theoretical analysis focussed on the number of steps that algorithms require to find the
optimal solution. To make a connection with calculus, compare an arbitrary tour x through n points with the optimal
(minimum-length) tour x∗ by considering the two quantities
{number of edges in x but not in x∗}
δn(x) =
,
n
1Research supported by N.S.F. Grant DMS0203062.
2Research supported in part by the EuroNGI network.
3Research supported by Science Foundation Ireland Grant SFI04/RP1/I512.

---

Near-minimal spanning trees: a scaling exponent in probability models
963
{length difference between x and x∗}
εn(x) =
,
s(n)
where s(n) is the length of the minimum length tour. Now define εn(δ) to be the minimum value of εn(x) over all
tours x for which δn(x) ≥ δ. Although the function εn(δ) will depend on n and the problem instance, we anticipate
that for typical instances drawn from a suitable probability model it will converge in the n → ∞ limit to some
deterministic function ε(δ). The universality paradigm from statistical physics [8] suggests there might be a scaling
exponent α defined by
ε(δ) ∼ δα
as δ → 0
and that the exponent should be robust under model details.
There is fairly strong evidence [1] that for TSP the scaling exponent is 3. This is based on analytic methods in a
mean-field model of interpoint distances (distances between pairs of points are random, independent for different pairs,
thus ignoring geometric constraints) and on Monte Carlo simulations for random points in 2, 3 and 4 dimensional
space. The analytic results build upon a recent probabilistic reinterpretation [2] of the work of Krauth and Mézard
[9] establishing the average length of mean-field TSP tours. But neither part of these TSP assertions is rigorous, and
indeed rigorous proofs in d dimensions seem far out of reach of current methodology. In contrast, for the minimum
spanning tree (MST) problem, a standard algorithmically easy problem, a simple heuristic argument (Section 1.2)
strongly suggests that the scaling exponent is 2 for any reasonable probability model. The goal of this paper is to work
through the details of a rigorous proof.
Why study such scaling exponents? For a combinatorial optimization problem, a larger exponent means that there
are more near-optimal solutions, suggesting that the algorithmic problem of finding the optimal solution is intrinsi-
cally harder. So scaling exponents may serve to separate combinatorial optimization problems of an appropriate type
into a small set of classes of increasing difficulty. For instance, the minimum matching and minimum Steiner tree prob-
lems are expected to have scaling exponent 3, and thus be in the same class as TSP in a quantitative way, as distinct
from their qualitative similarity as NP-complete problems under worst-case inputs. In contrast, algorithmically easy
problems are expected to have scaling exponent 2, analogously to the “calculus” scaling exponent. One plausible ex-
planation is that the near-optimal solutions in such problems differ from the optimal solution via only “local changes,”
each local change affecting only a number of edges which remains O(1) as δ → 0.
1.1. Background
Steele [11] and Yukich [13] give general background concerning combinatorial optimization over random points.
A network is a graph whose edges e have positive real lengths len(e). Let G be a finite connected network. Recall
the notion of a spanning tree (ST) T in G. Identifying T as a set of edges, write len(T ) =
len(e). A minimal
e∈T
spanning tree (MST) is a ST of minimal length; such a tree always exists but may not be unique. The classical
greedy algorithm (Kruskal’s algorithm [7]) for constructing a MST yields two fundamental properties which we
record without proof in Lemma 1.
Let Gt be the subnetwork consisting of those edges e of G with len(e) < t. For arbitrary vertices v, w define
perc(v, w) = inf{t: v and w in same component of Gt }.
(1)
For an edge e = (v, w) of G write perc(e) = perc(v, w) ≤ len(e) and also define the excess
exc(e) = len(e) − perc(e) ≥ 0.
Lemma 1. Suppose all the edge-lengths in G are distinct.
(a) There is a unique MST, say T , and it is specified by the criterion
e ∈ T
if and only if exc(e) = 0.
(b) For any vertices v, w
perc(v, w) = max len(e): e on path from v to w in T .

---

964
D. J. Aldous, C. Bordenave and M. Lelarge
1.2. The heuristic argument
Given a probability model for n random points and their interpoint lengths, define a measure μn(·) on (0, ∞) in terms
of the expectation
μn(0, x) = 1 E edges e: 0 < len(e) − perc(e) < x .
n
For any reasonable model with suitable scaling of edge-lengths we expect an n → ∞ limit measure μ(·), with a
density fμ(x) = dμ/dx having a non-zero limit fμ(0+) as x ↓ 0.
Now modify the MST by adding an edge e with len(e) − perc(e) = b, for some small b, to create a cycle; then delete
the longest edge e = e of that cycle, which necessarily has len(e ) = perc(e). This gives a spanning tree containing
exactly one edge not in the MST and having length greater by b. Repeat this procedure with every edge e for which
0 < len(e) − perc(e) < β, for some small β. For large n, the number of such edges should be nμn(0, β) ≈ n fμ(0+)β
to first order in β, and assuming there is negligible overlap between cycles, each of the new edges will increase the
tree length by ∼ β/2 on average. So we expect (Lemma 6)
δ(β) ∼ fμ 0+ β,
ε(β) ∼ fμ(0+)β2 .
2
This construction should yield essentially the minimum value of ε for given δ, so we expect
ε(δ) ∼
δ2
(2)
2fμ(0+)
and in particular we expect the scaling exponent to be 2.
1.3. Results
Our goal is to formalize the argument above in the context of the following two probability models for n random
points. Fix dimension d ≥ 2 (the case d = 1 is of course rather special).
Model 1 (The disordered lattice). Start with the discrete d-dimensional cube Cd = [
m
1, 2, . . . , m]d , so there are n =
md vertices and there are 2d edges at each non-boundary vertex. Then take the edge-lengths to be i.i.d. random
variables ξe, whose common distribution ξ has finite mean and some bounded continuous density function fξ (·).
Model 2 (Random Euclidean). Take the continuum d-dimensional cube [0, n1/d ]d of volume n. Put down n indepen-
dent uniformly distributed random points in this cube. Take the complete graph on these n vertices, with Euclidean
distance as edge-lengths.
The results of this paper will remain valid in a slightly more general framework than Model 2 in which points
are put down independently at random in the cube [0, n1/d ]d with common density f (n1/d x) on Rd , with f having
support on [0, 1]d and being bounded away from zero. To avoid technicalities, we restrict ourselves to the case f
constant.
Each model is set up so that nearest-neighbor distances are order 1 and the MST Tn has mean length of order n. To
formalize the ideas in the introduction we define the random variable
len(T
ε
n) − len(Tn)
n(δ) := min
: T \ Tn ≥ δn ,
(3)
n
n
where the minimum is over spanning trees T
\
n and where Tn
Tn is the set of edges in Tn but not in Tn.
Theorem 2. In either model, we have
(a)
lim sup δ−2 lim sup Eεn(δ) < ∞,
δ↓0
n

---

Near-minimal spanning trees: a scaling exponent in probability models
965
and,
(b)
lim inf δ−2 lim inf Eεn(δ) > 0.
δ↓0
n
Structure of the paper
In Section 2, we do calculations in the finite models: we prove Theorem 2 for Model 1 and part (a) of the theorem for
Model 2. In Section 3, we introduce the limit infinite random network (limit in the sense of local weak convergence [4])
and its associated minimal spanning forest. We show how results from continuum percolation theory allow us to show
part (b) of Theorem 2 for Model 2.
2. Proofs for the finite network
2.1. The upper bound: Model 1 with d = 2
We first consider Model 1 with d = 2 and then consider the other cases.
The upper bound rests upon a simple construction of near-minimal spanning trees, illustrated in Fig. 1.
The figure illustrates a particular kind of configuration. There is a 4-cycle of edges abcd where, for some x,
len(a) = x,
len(b) ∈ (x, x + δ),
len(c) < x,
len(d) < x
and where the eight other edges touching the cycle have lengths > x + δ. With such a configuration (within a larger
configuration on C2m), edges adc are in the MST, and edge b is not. We can modify the minimal spanning tree by
removing edge a and adding edge b; this creates a new spanning tree whose extra length equals len(b) − x.
Thus given a realization of the edge-lengths on the m × m discrete square, partition the square into adjacent 3 × 3
regions; on each region where the configuration is as in Fig. 1, make the modification above. This changes the MST Tn
into a certain near-minimal spanning tree Tn. On each 3 × 3 square, the probability of seeing the Fig. 1 configuration
equals
∞
8
q(δ) :=
f (x) F (x + δ) − F (x) F 2(x) 1 − F (x + δ) dx.
0
Here f and F are the density and distribution functions of edge-lengths. And the (unconditioned) increase in edge-
length of spanning tree caused by the possible modification equals
∞
x+δ
8
r(δ) :=
f (x)
(y − x)f (y) dy F 2(x) 1 − F (x + δ) dx.
0
x
Fig. 1. A special configuration on the 3 × 3 grid.

---

966
D. J. Aldous, C. Bordenave and M. Lelarge
Letting n → ∞ with fixed δ, and using the weak law of large numbers,
p
n−1 T \
→ 1
n
Tn
q(δ),
(4)
9
p
n−1 len(T
→ 1
n) − len(Tn)
r(δ).
(5)
9
Because we defined εn(·) in terms of spanning trees which differ from the MST by a non-random proportion of edges,
we need a detour to handle expectations over events of asymptotically zero probability. We defer the proof.
Lemma 3. (a) For any sequence T ∗
n of spanning trees, the sequence n−1 len(T ∗
n ) is uniformly integrable.
(b) There exist spanning trees Tn such that
T \
n
Tn ≥ an,
where an/n → 1/2.
Now consider the spanning tree T ∗
\
n defined to be Tn if n−1|Tn
Tn| ≥ 1 q(δ) and to be T
10
n if not. It follows
from (4,5) and Lemma 3 that
n−1 T ∗ \
n
Tn ≥ 1 q(δ),
for large n,
10
lim sup n−1E len T ∗ −
n
len(Tn) ≤ 1 r(δ).
n
9
Then from the definitions of q(δ), r(δ) and the assumption that f (·) is bounded it is easy to check
q(δ) ∼ cδ,
r(δ) ∼ 1 δq(δ) as δ ↓ 0
(6)
2
for a certain 0 < c < ∞. This establishes the upper bound (a) in Theorem 2.
Proof of Lemma 3. Part (a) is automatic because, writing
for the sum over all edges of C2
e
m, the sequence
n−1
ξ
e e is uniformly integrable. For (b), note that the cube C2
m with 2m(m − 1) edges can be regarded as a subgraph
of the discrete torus Z2m with 2m2 edges. Take a uniform random spanning tree Tn on Z2m, delete edges not in C2m and
add back boundary edges to make some (non-uniform) random spanning tree Tn on C2m. By symmetry of the torus we
have P(e ∈ Tn) = m2−1 for each edge e of the torus, and it follows that P(e ∈ T
for each non-boundary edge
2m2
n) = m2−1
2m2
of the cube. Since there are 4(m − 1) boundary edges and 2(m − 1)(m − 2) non-boundary edges, for any spanning
tree t we have
E|T
m2 − 1
n ∩ t| ≤ 4(m − 1) + (n − 1)
= 4 n1/2 − 1 + (n − 1)2 .
2m2
2n
So
E|Tn \ t| = (n − 1) − E|Tn ∩ t|
≥ an := (n − 1) − 4 n1/2 − 1 − (n − 1)2 .
2n
So for any spanning tree t there exists some spanning tree t∗ such that |t∗ \ t| ≥ an. Applying this fact to the MST
gives (b).

---

Near-minimal spanning trees: a scaling exponent in probability models
967
Fig. 2. A special configuration on the 3 × 3 square.
2.2. Upper bound: Other cases
The argument for Model 1 in the case d ≥ 3 involves only very minor modifications of the proof above, so we turn to
Model 2 with d = 2 (the case d ≥ 3 is similar). Here it is natural to consider a different notion of special configuration,
see Figure 2.
Here there is a 3 × 3 square containing a concentric 1 × 1 square. There are three points within the larger square, all
being inside the smaller square. In the triangle abc formed by the three points, writing x for the length of the second
longest edge length, the length of the longest edge is in the interval (x, x + δ), and x + δ < 1. For such a configuration
(within a configuration on a m × m square containing the 3 × 3 square), edges ac are in the MST, and edge b is not.
We can modify the minimal spanning tree by removing edge a and adding edge b; this creates a new spanning tree
whose extra length equals len(b) − x.
We now repeat the argument from the previous section, and the overall logic is the same. One gets different formulas
for q(δ), r(δ) but they have the same relationship (6). The weak law (4), (5) is easily established. The only non-trivial
difference is that we need to replace the technical Lemma 3 by the following technical lemma.
Lemma 4. (a) There exists c1 such that for any n and any configuration on n points in the square of area n, the MST
ˆTn has len( ˆTn) ≤ c1n.
(b) For sufficiently large n, there exist spanning trees Tn such that len(Tn ) ≤ 12c1n and
n−1 T \
n
Tn ≥ 1 .
2
Proof. Part (a) follows from the analogous result for TSP – see [11] inequality (2.14). For (b), let ξ1, . . . , ξn be the
positions of the n random points and recall that Tn is their MST. Classify these points ξi as “odd” or “even” according
to whether the number of edges in the path inside Tn from ξi to ξ1 is odd or even. Let (ˆξi) be a configuration obtained
from (ξi) by moving each “odd” point a distance 11c1 in some arbitrary direction. Let ˆ
Tn be the MST on (ˆξi). Let Tn
be the spanning tree on (ξi) defined by
(ξi, ξj ) ∈ Tn
iff ( ˆξi, ˆξj ) ∈ ˆ
Tn.
Suppose (ξi, ξj ) is an edge of both Tn and Tn . Since one end-vertex is odd and the other is even, it is easy to see: either
(i) len(ξi, ξj ) ≥ 5c1; or (ii) len(ˆξi, ˆξj ) ≥ 5c1. But by part (a) there are at most n/5 edges satisfying (i), and similarly
for (ii). So |Tn ∩ T | ≤
n
2n/5. Noting that
len T
≤
n
11c1(n − 1) + len( ˆ
Tn) ≤ 12c1n
using (a), we have established (b).
2.3. The lower bound: A discrete lemma
The lower bound argument rests upon the following simple lemma.

---

968
D. J. Aldous, C. Bordenave and M. Lelarge
Lemma 5. Consider a finite connected network with distinct edge-lengths. If T is the MST and T is any ST then
len T
− len(T ) ≥
exc e .
e ∈T \T
Proof. Suppose |T \ T | = k ≥ 1. It is enough to show that there exist e ∈ T \ T and e ∈ T \ T such that
(i) T ∗ = T \ {e } ∪ {e} is a ST;
(ii) |T ∗ \ T | = k − 1;
(iii) len(e ) − len(e) ≥ exc(e )
for then we can continue inductively.
To prove this we first choose an arbitrary e ∈ T \ T . Consider T \ {e }. This is a two-component forest; so the
path in T linking the end-vertices of e must contain some edge e ∈ T \ T which links these two components. So
choose some such edge e. Properties (i) and (ii) are clear. Apply Lemma 1(b) to the end-vertices of e to see that
perc(e ) ≥ len(e). So
len e − len(e) ≥ len e − perc e = exc e
which is (iii).
We will also need the following integration lemma; part (a) will be used for Model 1 and part (b) for Model 2.
Lemma 6. (a) Let ξ and W be independent real-valued random variables such that ξ has a density function bounded
by a constant b. Then for any event A ⊆ {ξ > W } we have
P2
E
(A)
(ξ − W )1A ≥
.
2b
(b) Let (V
μ(0,x)
i , i ≥ 1) be real-valued r.v.’s such that μ(0, x) := E
1
< ∞. Then
i
(0<Vi <x) satisfies lim supx↓0
x
there exists a function g(s) ∼ βs2 as s ↓ 0, for some β > 0, such that for any sequence of events Ai ⊆ {Vi > 0},
E
Vi1A ≥ g
P(A
i
i ) .
i
i
Proof. (a) It is sufficient to prove
P2
E
(A|W )
(ξ − W )1A|W ≥
a.s.,
(7)
2b
then by Jensen’s inequality, we get
E[P2
P2
E E
(A|W )]
(A)
(ξ − W )1A|W
≥
≥
.
2b
2b
Since ξ and W are independent of each other, Eq. (7) reduces to
P2
E[
(A)
ξ 1A] ≥
for A ⊆ {ξ > 0}.
2b
We can couple ξ to a r.v. U such that
(i) U = 0 on {ξ ≤ 0}.
(ii) U has constant density b on (0, P(ξ > 0)/b).
(iii) U ≤ ξ .

---

Near-minimal spanning trees: a scaling exponent in probability models
969
Now it suffices to prove
P2
E[
(A)
U 1A] ≥
for A ⊆ {U > 0}.
(8)
2b
But it is clear that, for a given value of P(A), the choice of A ⊆ {U > 0} that minimizes E[U 1A] is of the form
Ac := {0 < U < c} for some c < P(ξ > 0)/b. A brief calculation gives
P2
E[
(Ac)
U 1A ] =
c
2b
establishing (8).
(b) For small s > 0 define g(s) by
c(s)
g(s) =
xμ(dx),
where μ 0, c(s) = s.
0
By hypothesis there exists γ > 0 such that c(s) ≥ γ s for small s. So
c(s)
s
g(s) ≥
xμ(dx) ≥ c
× s = γ s2 .
c(s/2)
2
2
4
Taking As := {0 < V
i
i ≤ c(s)} we have
c(s)
P As = μ 0, c(s) = s;
E
V
=
xμ(dx) = g(s).
i
i 1Asi
i
i
0
This is clearly the choice of (Ai) which minimizes the left side subject to
P(A
i
i ) = s, and so for arbitrary (Ai ) we
have
E
Vi1A ≥ g
P(A
i
i ) .
i
i
2.4. The lower bound in Model 1
We treat the case d = 2, but d ≥ 3 involves only minor changes. Recall C2 =
m
G(n) has cn := 2(n − n1/2) edges. Fix
δ > 0. Consider a pair (Tn, Tn) attaining the minimum in the definition (3) of εn(δ). For a uniform random edge en
of C2m,
E| \
P
T
Tn|
e
n
n ∈ T \
≥ δ
n
Tn =
(9)
cn
2
and
Eεn(δ) = 1 E len T − len(Tn)
n
n
≥ 1 E
exc(e)
by Lemma 5
n
e∈T \
n Tn
= cn E exc(en)1(e
\T
n
n∈Tn
n).
(10)
For a fixed edge e of C2m we can write
+
exc(e) = ξ (n)(e) − W (n)(e)

---

970
D. J. Aldous, C. Bordenave and M. Lelarge
where ξ (n)(e) is the edge-length of e = (v, v∗) and where
W (n)(e) = inf t: v and v∗ in the same component of G(n) \ {
t
e} .
Note (and this is the key special feature that makes Model 1 easy to study) that ξ (n)(e) and W (n)(e) are independent.
Since exc(e) > 0 on {e ∈ T \
n
Tn} we see that the quantity at (10) is of the form appearing in Lemma 6(a). So
n Eεn(δ) ≥ E ξ(n)(en) − W(n)(en) 1(e \T
c
n∈Tn
n)
by (10)
n
P2
\
≥
(en ∈ Tn Tn) by Lemma 6(a)
2 ¯
f
≥ δ2
by (9),
8 ¯
f
where ¯
f is the bound on the density of ξ . Because cn ∼ 2n we have established part (b) of Theorem 2 in this case.
3. The minimum spanning forest and continuum percolation
It remains to prove the lower bound in Model 2. Rather than doing calculations with the finite model, we consider
the limit Poisson process on the plane, and exploit the well known connection between the minimum spanning forest
(MSF) and continuum percolation. We then relate the finite models to the infinite limits in Section 3.3, as an instance
of local weak convergence [4] of random graphical structures.
3.1. Minimum spanning forests
Here is a general definition, in the context of a countable-vertex network G with distinct edge-lengths (see [5] for
more detailed treatment). As in Section 1.1 let Gt be the subnetwork consisting of those edges e of G with len(e) < t.
Define the MSF by:
an edge (v, w) is in the MSF if and only if, for t = len(v, w), vertices v and w are in different components of Gt
and at least one of these components is finite.
Consider a Poisson point process Φ =
δ
of rate 1 in Rd . Add an extra point O at the origin. Consider ΦO =
i ηi
δ
+ δ
i ηi
O as the vertices of a network G (the complete graph with Euclidean edge-lengths). With probability one,
ΦO has only finitely many points in any bounded subset of Rd and all of the interpoint distances are distinct. As in
Section 1.1, we define for arbitrary points ηi and ηj of ΦO ,
perc(ηi, ηj ) = inf{t: ηi and ηj are in the same component of Gt }.
We now give some properties of the MSF denoted F∞ on this network and show how Lemma 1 extends to this
setting.
Lemma 7. (a) We have e ∈ F∞ if and only if len(e) = perc(e).
(b) For any vertex-pair u, v write u → v for the set of paths π from u to v. Then, a.s.
perc(u, v) = min max len(e): e ∈ π .
(11)
π :u→v
Proof. Let us say that G has the uniqueness property if for every vertex-pair u, v ∈ G, the graph Glen(u,v) has at most
one infinite component (note that this notion was used in the proof of Lemma 2.1 in [12]). Part (a) will follow from

---

Near-minimal spanning trees: a scaling exponent in probability models
971
the fact that ΦO has the uniqueness property, which implies:
e = (v, w) ∈ F∞
⇐⇒ v and w are in different components of Glen(e)
⇐⇒ perc(e) ≥ len(e)
⇐⇒ perc(e) = len(e).
To show that ΦO has the uniqueness property almost surely it is enough to show
P ∀u ∈ ΦO, Glen(O,u) has at most one infinite component = 1.
(12)
This last fact follows from Theorem 1.8 (and Remark 1.10) of [6], which implies (see also [5]),
P(Gt includes at most one infinite component for each t ∈ R) = 1.
(13)
Note that (12) can be proved without appealing to the simultaneous uniqueness result as follows:
P ∀u ∈ ΦO, Glen(O,u) has at most one infinite component
= lim P ∀u ∈ ΦO ∩ B(n), Glen(O,u) has at most one infinite component
n→∞
≥ lim P ∀u ∈ ΦO ∩ B(n), Glen(O,u) \ B(n) has at most one infinite component ,
n→∞
where B(n) is the ball of center the origin and radius n and for any network G on Rd , G \ B(n) is the subnetwork
with edges and vertices in Rd \ B(n). By independence and the fact that there can be at most one infinite component
in continuum percolation (see Theorem 3.6 in [10]), we have
P ∀u ∈ ΦO ∩ B(n), Glen(O,u) \ B(n) has at most one infinite component ΦO ∩ B(n) = 1 a.s.
which proves (12).
We now prove (b). Let t = perc(u, v), the definition of perc(u, v) may be restated easily as:
t = perc(u, v) = inf max len(e): e ∈ π .
π : u→v
Hence (b) amounts to prove that with probability one, this infimum is indeed a minimum. Note that Gt (u) ∩ Gt (v) = ∅
and by (13) a.s. at least one of these two clusters, say Gt (u), is finite. Let E be the set of edges with exactly one of
its end vertices in Gt (u) and the other one in Gt (u)c, and with edge length less than t + 1. The set E is a.s. finite
and then we easily see that min{len(e), e ∈ E} = t = perc(u, v) since u and v are in the same component of Gt+
for any
> 0. Let e∗ = arg min{len(e), e ∈ E} and write e∗ = (a, b) with a ∈ Gt (u) and b ∈ Gt (u)c. Since a.s.
we have len(e) = len(e∗) = t for any e = e∗, a.s. we have Gt+(u) :=
>0 Gt+ (u) = Gt (u) ∪ {e∗} ∪ Gt (b) and
Gt+(v) = Gt (v). But the definition of t = perc(u, v) implies that Gt+(u) = Gt+(v), and hence b ∈ Gt (v). It follows
that
inf max len(e): e ∈ π = len e∗ = min max len(e): e ∈ π ,
π :u→v
π :u→v
and (b) follows.
3.2. Finite density
Define the measure μ on (0, +∞) by
μ(0, x) = E
1 0 < len(O, ηi) − perc(O, ηi) < x
i
= E
1 0 < len(O, ηi) − perc(O, ηi) ≤ x .
i

---

Document Outline

• Introduction
  • Background
  • The heuristic argument
  • Results
  • Structure of the paper
• Proofs for the finite network
  • The upper bound: Model 1 with d=2
  • Upper bound: Other cases
  • The lower bound: A discrete lemma
  • The lower bound in Model 1
• The minimum spanning forest and continuum percolation
  • Minimum spanning forests
  • Finite density
  • The lower bound in Model 2
• References

---