LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "Tài liệu Đề tài " Geometry of the uniform spanning forest: Transitions in dimensions 4, 8, 12, . . . " pptx": http://123doc.vn/document/1036269-tai-lieu-de-tai-geometry-of-the-uniform-spanning-forest-transitions-in-dimensions-4-8-12-pptx.htm
subgraph of Z
d
). Then let τ :=
{x,y}∈τ
xy denote the product of xy over
all undirected edges {x, y} in τ . Define the spread of W by W := min
τ
τ,
where τ ranges over all trees on the vertex set W .
For three vertices, xyz = min{xyyz, yzzx, zxxy}. More gen-
erally, for n vertices, x
1
x
n
is a minimum of n
n−2
products (since this
is the number of trees on n labeled vertices); see Remark 2.7 for a simpler
equivalent expression.
Definition 2.2 (Stochastic dimension). Let R be a random subset of
Z
d
× Z
d
. We think of R as a relation, and usually write xRy instead of
(x, y) ∈R. Let α ∈ [0,d). We say that R has stochastic dimension d − α, and
write dim
S
(R)=d − α, if there is a constant C = C(R) < ∞ such that
C P[xRz] ≥xz
−α
,(2.1)
and
P[xRz, yRw] ≤ C xz
−α
yw
−α
+ C xzyw
−α
,(2.2)
hold for all x, y, z, w ∈ Z
d
.
Observe that (2.2) implies
P[xRz] ≤ 2C xz
−α
,(2.3)
since we may take x = y and z = w. Also, note that dim
S
(R)=d if and only
if inf
x,z∈
Z
d
P[xRz] > 0.
To motivate (2.2), focus on the special case in which R is a random equiv-
alence relation. Then heuristically, the first summand in (2.2) represents an
upper bound for the probability that x, z are in one equivalence class and y,w
are in another, while the second summand, C xzyw
−α
, represents an upper
bound for the probability that x, z, y, w are all in the same class. Indeed,
when the equivalence classes are the components of the USF, we will make
this heuristic precise in Section 4.
Several examples of random relations that have a stochastic dimension
are described in Section 6. The main result of Section 4, Theorem 4.2, asserts
that the relation determined by the components of the USF has stochastic
dimension 4.
Definition 2.3 (Composition). Let L, R⊂Z
d
× Z
d
be random relations.
The composition LR of L and R is the set of all (x, z) ∈ Z
d
× Z
d
such that
there is some y ∈ Z
d
with xLy and yRz.
Composition is clearly an associative operation, that is, (LR)Q = L(RQ).
Our main goal in this section is to prove,
GEOMETRY OF THE UNIFORM SPANNING FOREST
469
Theorem 2.4. Let L, R⊂Z
d
× Z
d
be independent random relations.
Then
dim
S
(LR) = min
dim
S
(L) + dim
S
(R),d
,
when dim
S
(L) and dim
S
(R) exist.
Notation. We write φ ψ (or equivalently, ψ φ), if φ ≤ Cψ for some
constant C>0, which may depend on the laws of the relations considered.
We write φ ψ if φ ψ and φ ψ.Forv ∈ Z
d
and 0 ≤ n<N, define the
dyadic shells
H
N
n
(v):={x ∈ Z
d
:2
n
≤vx < 2
N
}.
Remark 2.5. As the proof will show, the composition rule of Theorem 2.4
for random relations in Z
d
is valid for any graph where the shells H
k+1
k
(v)
satisfy |H
k+1
k
(v)|2
dk
.
For sets V,W ⊂ Z
d
let
ρ(V,W) := min{vw : v ∈ V, w ∈ W }.
In particular, if V and W have nonempty intersection, then ρ(V, W)=1. We
write Wx as an abbreviation for W ∪{x}.
Lemma 2.6. For every M>0, every x ∈ Z
d
and every W ⊂ Z
d
with
|W |≤M,
Wx≤W ρ(x, W ) Wx ,
where the constant implicit in the notation depends only on M.
Proof. We may assume without loss of generality that x/∈ W. The
inequality Wx≤W ρ(x, W ) holds because given a tree on W we may obtain
a tree on W ∪{x} by adding an edge connecting x to the closest vertex in W .
For the second inequality, consider some tree τ with vertices W ∪{x}. Let W
denote the neighbors of x in τ, and let u ∈ W
be such that xu = ρ(x, W
).
Let τ
be the tree on W obtained from τ by replacing each edge {w
,x} where
w
∈ W
\{u}, by the edge {w
,u}. (See Figure 2.1.) It is easy to verify that
τ
is a tree. For each w
∈ W
, we have uw
≤ux + xw
≤2xw
. Hence
τ
ux≤2
M
τ, and the inequality W ρ(x, W) ≤ 2
M
Wx follows.
470 ITAI BENJAMINI, HARRY KESTEN, YUVAL PERES, AND ODED SCHRAMM
τ
τ
u
x
u
Figure 2.1: The trees τ and τ
.
Remark 2.7. Repeated application of Lemma 2.6 yields that for any set
{x
1
, ,x
n
} of n vertices in Z
d
,
x
1
x
n
n−1
i=1
ρ(x
i
, {x
i+1
, ,x
n
}) ,(2.4)
where the implied constants depend only on n.
Our next goal in the proof of Theorem 2.4 is to establish (2.1) for the
composition LR. For this, the following lemma will be essential.
Lemma 2.8. Let L and R be independent random relations in Z
d
. Sup-
pose that dim
S
(L)=d−α and dim
S
(R)=d−β exist, and denote γ := α+β−d.
For u, z ∈ Z
d
and 1 ≤ n ≤ N, let
S
uz
= S
uz
(n, N):=
x∈H
N +1
n
(u)
1
uLx
1
xRz
.
If uz < 2
n−1
and N ≥ n, then
P[S
uz
> 0]
N
k=n
2
−kγ
N
k=0
2
−kγ
.(2.5)
Proof.Fork ≥ n and x ∈ H
k+1
k
(u), we have P[uLx] 2
−kα
(use (2.1)
and (2.3)). Also, for x ∈ H
k+1
k
(u), k ≥ n,
1
2
xu≤xu−zu≤xz≤xu + zu≤2xu
and P[xRz] 2
−kβ
.
Because L and R are independent and |H
k+1
k
(u)|2
dk
,wehave
E[S
uz
]
N
k=n
2
kd
2
−kα
2
−kβ
=
N
k=n
2
−kγ
.(2.6)
GEOMETRY OF THE UNIFORM SPANNING FOREST
471
To estimate the second moment, observe that if 2uz≤ux≤uy, then
uy≤uz + zy≤
1
2
uy + zy ,
so that xy≤xu+uy≤2uy≤4yz. Applying the first two inequalities
here, (2.2) for L and Lemma 2.6, we obtain that
P[uLx, uLy] ux
−α
uy
−α
+ uxy
−α
ux
−α
uy
−α
+ xy
−α
ux
−α
xy
−α
.
Similarly, from Lemma 2.6 and the inequality xy≤4yz above, it follows
that
P[xRz,yRz] xz
−β
xy
−β
+ yz
−β
xz
−β
xy
−β
.
Since
E[S
2
uz
] ≤ 2
x∈H
N +1
n
(u)
y∈H
N +1
n
(u)
1
{uy≥ux}
P[uLx, uLy]P[xRz, yRz],
we deduce by breaking the inner sum up into sums over y ∈ H
j+1
j
(x) for various
j that
E[S
2
uz
]
x∈H
N +1
n
(u)
ux
−α
xz
−β
y∈H
N +2
0
(x)
xy
−α−β
E[S
uz
]
N
j=0
2
j(d−α−β)
.
(2.7)
Finally, recall that γ = α + β − d, and apply the Cauchy-Schwarz inequality
in the form
P[S
uz
> 0] ≥
E[S
uz
]
2
E[S
2
uz
]
.
The estimates (2.6) and (2.7) then yield the assertion of the lemma.
Corollary 2.9. Under the assumptions of Theorem 2.4, P[uLRz]
uz
−γ
for all u, z ∈ Z
d
, where γ
:= max
0,d− dim
S
(L) − dim
S
(R)
.
Proof. Let n := log
2
uz + 2 and γ := α + β − d with α := d − dim
S
(L),
β := d − dim
S
(R). Apply the lemma with N := n if γ = 0 and N := 2n if
γ =0.
The proof of (2.2) for the composition LR requires some further prepara-
tion.
Lemma 2.10. Let α, β ∈ [0,d) satisfy α + β>d.Letγ := α + β − d.
Then for v, w ∈ Z
d
,
x∈
Z
d
vx
−α
xw
−β
vw
−γ
.
472 ITAI BENJAMINI, HARRY KESTEN, YUVAL PERES, AND ODED SCHRAMM
Proof. Suppose that 2
N
≤vw≤2
N+1
. By symmetry, it suffices to sum
over vertices x such that xv≤xw. For such x in the shell H
n+1
n
(v), we
have by the triangle inequality
xv
−α
xw
−β
2
−nα
2
− max{n,N }β
.
Multiplying by 2
dn
(for the volume of the shell) and summing over all n prove
the lemma.
Lemma 2.11. Let M>0 be finite and let V,W ⊂ Z
d
satisfy |V |, |W |
≤ M .Letα, β ∈ [0,d) satisfy α + β>d. Denote γ := α + β − d. Then
x∈
Z
d
Vx
−α
Wx
−β
V
−α
ρ(V,W)
−γ
W
−β
≤VW
−γ
,(2.8)
where the constant implicit in the relation may depend only on M.
Proof. Using Lemma 2.6 we see that
Vx
−α
V
−α
ρ(x, V )
−α
≤V
−α
v∈V
vx
−α
and similarly Wx
−β
W
−β
w∈W
wx
−β
. Therefore, by Lemma 2.10,
x∈
Z
d
Vx
−α
Wx
−β
V
−α
W
−β
v∈V
w∈W
vw
−γ
≤ M
2
V
−α
W
−β
ρ(V,W)
−γ
.
The rightmost inequality in (2.8) holds because γ ≤ min{α, β} and given trees
on V and on W , a tree on V ∪ W can be obtained by adding an edge {v, w}
with v ∈ V, w ∈ W and vw = ρ(V, W) (unless V ∩ W = ∅, in which case
|V ∩ W|−1 edges have to be deleted to obtain a tree on V ∪ W).
Lemma 2.12. Let α, β ∈ [0,d) satisfy γ := α + β − d>0. Then
a∈
Z
d
ax
−α
ay
−β
az
−γ
xyz
−γ
holds for x, y, z ∈ Z
d
.
Proof. Without loss of generality, we may assume that zx≤zy. Con-
sider separately the sum over A := {a : az≤
1
2
zx} and its complement.
For a ∈ A we have ax≥
1
2
zx and ay≥
1
2
zy. Therefore,
a∈A
ax
−α
ay
−β
az
−γ
zx
−α
zy
−β
a∈A
az
−γ
zx
−α
zy
−β
zx
d−γ
= zx
−γ
zy
−γ
zx
d−α
zy
d−α
≤xyz
−γ
,
GEOMETRY OF THE UNIFORM SPANNING FOREST
473
because of the assumption zx≤zy and γ>0. Passing to the complement
of A,wehave,
a∈
Z
d
\A
az
−γ
ax
−α
ay
−β
zx
−γ
a∈
Z
d
ax
−α
ay
−β
zx
−γ
xy
−γ
≤xyz
−γ
,
where Lemma 2.10 was used in the next to last inequality. Combining these
two estimates completes the proof of the lemma.
The following slight extension of Lemma 2.12 will also be needed. Under
the same assumptions on α, β, γ,
a∈
Z
d
axw
−α
ay
−β
az
−γ
xwyz
−γ
.(2.9)
This is obtained from Lemma 2.12 by using axw xw min
ax, aw
,
which is an application of Lemma 2.6, and xwwyz≥xwyz, which holds
by the definition of the spread.
Proof of Theorem 2.4. If dim
S
(L) + dim
S
(R) ≥ d, then Corollary 2.9
shows that
inf
x,y∈
Z
d
P[xLRy] > 0 ,
which is equivalent to dim
S
(LR)=d. Therefore, assume that dim
S
(L)+
dim
S
(R) <d. Let α := d − dim
S
(L), β := d − dim
S
(R) and γ := α + β − d.
Since Corollary 2.9 verifies (2.1) for the composition LR, it suffices to prove
(2.2) for LR with γ in place of α. Independence of the relations L and R,
together with (2.2) for L and for R with β in place of α imply
P[xLRz, yLRw] ≤
a,b∈
Z
d
P[xLa, yLb]P[aRz, bRw](2.10)
a,b∈
Z
d
xa
−α
yb
−α
+ xayb
−α
az
−β
bw
−β
+ azbw
−β
.
Opening the parentheses gives four sums, which we deal with separately. First,
a,b∈
Z
d
xa
−α
yb
−α
az
−β
bw
−β
xz
−γ
yw
−γ
,(2.11)
by Lemma 2.10 applied twice. Second, by two applications of Lemma 2.11,
a∈
Z
d
b∈
Z
d
xayb
−α
azbw
−β
(2.12)
a∈
Z
d
ρ
{x, a, y}, {z, a, w}
−γ
xay
−α
zaw
−β
=
a∈
Z
d
xay
−α
zaw
−β
xyzw
−γ
.
474 ITAI BENJAMINI, HARRY KESTEN, YUVAL PERES, AND ODED SCHRAMM
Third, by Lemma 2.11 and (2.9),
(2.13)
a∈
Z
d
b∈
Z
d
xayb
−α
az
−β
bw
−β
a∈
Z
d
ρ
w, {x, y, a}
−γ
az
−β
xay
−α
≤
a∈
Z
d
wa
−γ
az
−β
xay
−α
+ ρ
w, {x, y}
−γ
a∈
Z
d
az
−β
xay
−α
wzxy
−γ
+ ρ
w, {x, y}
−γ
zxy
−γ
≤ 2wzxy
−γ
.
By symmetry, we also have
a,b∈
Z
d
xa
−α
yb
−α
azbw
−β
xywz
−γ
.
This, together with (2.10), (2.11), (2.12) and (2.13), implies that LR satisfies
the correlation inequality (2.2) with γ in place of α, and completes the proof.
3. Tail triviality
Consider the USF on Z
d
. Given n =1, 2, , let R
n
be the relation
consisting of all pairs (x, y) ∈ Z
d
× Z
d
such that y may be reached from x by a
path which uses no more than n − 1 edges outside of the USF. We show below
that R
1
has stochastic dimension 4 (Theorem 4.2) and that R
n
stochastically
dominates the composition of n independent copies of R
1
(Theorem 4.1). By
Theorem 2.4, R
n
dominates a relation with stochastic dimension min{4n, d}.
When 4n ≥ d, this says that inf
x,y∈
Z
d
P[xR
n
y] > 0. For Theorem 1.1, the
stronger statement that inf
x,y∈
Z
d
P[xR
n
y] = 1 is required. For this purpose,
tail triviality needs to be discussed.
Definition 3.1 (Tail triviality). Let R⊂Z
d
× Z
d
be a random relation
with law P. For a set Λ ⊂ Z
d
× Z
d
, let F
Λ
be the σ-field generated by the
events xRy,(x, y) ∈ Λ. Let the left tail field F
L
(v) corresponding to a vertex
v be the intersection of all F
{v}×K
where K ⊂ Z
d
ranges over all subsets such
that Z
d
K is finite. Let the right tail field F
R
(v) be the intersection of all
F
K×{v}
where K ⊂ Z
d
ranges over all subsets such that Z
d
K is finite. Let
the remote tail field F
W
be the intersection of all F
K
1
×K
2
, where K
1
,K
2
⊂ Z
d
range over all subsets of Z
d
such that Z
d
K
1
and Z
d
K
2
are finite. The
random relation R with law P is said to be left tail trivial if P[A] ∈{0, 1} for
every A ∈ F
L
(v) and every v ∈ Z
d
. Analogously, define right tail triviality and
remote tail triviality.
GEOMETRY OF THE UNIFORM SPANNING FOREST
475
We will need the following known lemma, which is a corollary of the
main result of von Weizs¨acker (1983). Its proof is included for the reader’s
convenience.
Lemma 3.2. Let {F
n
} and {G
n
} be two decreasing sequences of complete
σ-fields in a probability space (X, F,µ), with G
1
independent of F
1
, and let
T denote the trivial σ-field, consisting of events with probability 0 or 1.If
∩
n≥1
F
n
= T = ∩
n≥1
G
n
, then ∩
n≥1
(F
n
∨ G
n
)=T as well.
Proof. Let h ∈
∞
n=1
L
2
(F
n
∨ G
n
). It suffices to show that h is constant.
Suppose that f
n
∈ L
2
(F
n
), g
n
∈ L
∞
(G
n
) and f ∈ L
∞
(F
1
). Then
E[f
n
g
n
f|G
1
]=g
n
E[f
n
f|G
1
]=g
n
E[f
n
f]a.s.
As the linear span of such products f
n
g
n
is dense in L
2
(F
n
∨ G
n
), it follows
that
E[hf|G
1
] ∈ L
2
(G
n
) .(3.1)
By our assumption T = ∩
n≥1
G
n
, we infer from (3.1) that
E[hf|G
1
]=E[hf] for f ∈ L
∞
(F
1
).(3.2)
In particular, E[h|G
1
]=E[h]. By symmetry, E[h|F
1
]=E[h], whence
∀f ∈ L
∞
(F
1
), E[hf]=E
fE[h|F
1
]
= E[h]E[f ] .
Inserting this into (3.2), we conclude that for f ∈ L
∞
(F
1
) and g ∈ L
∞
(G
1
) (so
that f and g are independent),
E[hfg]=E
gE[hf|G
1
]
= E[h]E[f ]E[g]=E[h]E[fg] .
Thus h − E[h] is orthogonal to all such products fg, so it must vanish a.s.
Suppose that R, L⊂Z
d
×Z
d
are independent random relations which have
trivial remote tails and trivial left tails, and have stochastic dimensions. We
do not know whether it follows that LR is left tail trivial. For that reason, we
introduce the notion of the restricted composition LR, which is the relation
consisting of all pairs (x, z) ∈ Z
d
× Z
d
such that there is some y ∈ Z
d
with xLy
and yRz and
xz≤min{xy, yz} .(3.3)
Theorem 3.3. Let R, L⊂Z
d
× Z
d
be independent random relations.
(i) If L has trivial left tail and R has trivial remote tail, then the restricted
composition LR has trivial left tail.
(ii) If dim
S
(L) and dim
S
(R) exist, then
dim
S
(LR) = min{dim
S
(L) + dim
S
(R),d} .
476 ITAI BENJAMINI, HARRY KESTEN, YUVAL PERES, AND ODED SCHRAMM
(iii) If dim
S
(L) and dim
S
(R) exist, L has trivial left tail, R has trivial right
tail and dim
S
(L) + dim
R
(R) ≥ d, then P[xLRz]=1for all x, z ∈ Z
d
.
Proof. (i) This is a consequence of Lemma 3.2.
(ii) Denote γ
:= max{0,d− dim
S
(L) − dim
R
(R)}. The inequality P[xL
Rz] xz
−γ
follows from the proof of Corollary 2.9; this concludes the proof
if γ
=0. Ifγ
> 0, then the required upper bound for P[x LRz, y LRw]
follows from Theorem 2.4, since LRis a subrelation of LR.
(iii) Let F
n
(respectively, G
n
) be the (completed) σ-field generated by the
events uLx (respectively, xRz)asx ranges over H
∞
n
(u). The event
A
n
:= {∃x ∈ H
2n
n
(u):uLx, xRz}
is clearly in F
n
∨ G
n
. By Lemma 2.8, there is a constant C such that P[A
n
] ≥
1/C > 0, provided that n is sufficiently large. Let A = ∩
k≥1
∪
n≥k
A
n
be the
event that there are infinitely many x ∈ Z
d
satisfying uLx and xRz. Then
P[A] ≥ 1/C. By Lemma 3.2, P[A]=1.
Corollary 3.4. Let m ≥ 2, and let {R
i
}
m
i=1
be independent random
relations in Z
d
such that dim
S
(R
i
) exists for each i ≤ m. Suppose that
m
i=1
dim
S
(R
i
) ≥ d,
and in addition, R
1
is left tail trivial, each of R
2
, ,R
m−1
has a trivial remote
tail, and R
m
is right tail trivial. Then P[uR
1
R
2
···R
m
z]=1for all u, z ∈ Z
d
.
Proof. Let L
1
= R
1
and define inductively L
k
= L
k−1
R
k
for k =
2, ,m, so that L
k
is a subrelation of R
1
R
2
R
k
. It follows by induction
from Theorem 3.3 that L
k
has a trivial left tail for each k<m, and
dim
S
(L
k
) = min
k
i=1
dim
S
(R
i
),d
.
By Theorem 3.3(iii), the restricted composition L
m
= L
m−1
R
m
satisfies
P[uL
m
z] = 1 for all u, z ∈ Z
d
.(3.4)
4. Relevant USF properties
Basic to the understanding of the USF is a procedure from BLPS [2]
that generates the (wired) USF on any transient graph; it is called “Wilson’s
method rooted at infinity”, since it is based on an algorithm from Wilson [15]
for picking uniformly a spanning tree in a finite graph. Let {v
1
,v
2
, } be an
GEOMETRY OF THE UNIFORM SPANNING FOREST
477
arbitrary ordering of the vertices of a transient graph G. Let X
1
be a simple
random walk started from v
1
. Let F
1
denote the loop-erasure of X
1
, which is
obtained by following X
1
and erasing the loops as they are created. Let X
2
be
a simple random walk from v
2
which stops if it hits F
1
, and let F
2
be the union
of F
1
with the loop-erasure of X
2
. Inductively, let X
n
be a simple random
walk from v
n
, which is stopped if it hits F
n−1
, and let F
n
be the union of F
n−1
with the loop-erasure of X
n
. Then F :=
∞
n=1
F
n
has the distribution of the
(wired) USF on G. The edges in F inherit the orientation from the loop-erased
walks creating them, and hence F may be thought of as an oriented forest. Its
distribution does not depend on the ordering chosen for the vertices. See BLPS
[2] for details.
We say that a random set A stochastically dominates a random set Q if
there is a coupling µ of A and Q such that µ[A ⊃ Q]=1.
Theorem 4.1 (Domination). Let F, F
0
,F
1
,F
2
, ,F
m
be independent
samples of the wired USF in the graph G.LetC(x, F ) denote the vertex set
of the component of x in F . Fix a distinguished vertex v
0
in G, and write
C
0
= C(v
0
,F).Forj ≥ 1, define inductively C
j
to be the union of all vertex com-
ponents of F that are contained in, or adjacent to, C
j−1
.LetQ
0
= C(v
0
,F
0
).
For j ≥ 1, define inductively Q
j
to be the union of all vertex components of F
j
that intersect Q
j−1
. Then C
m
stochastically dominates Q
m
.
Proof. For each R>0 let B
R
:=
v ∈ Z
d
: |v| <R
, where |v| is the
graph distance from v
0
to v. Fix R>0. Let B
W
R
be the graph obtained from
G by collapsing the complement of B
R
to a single vertex, denoted v
∗
R
. Let
F
,F
0
, ,F
m
be independent samples of the uniform spanning tree (UST) in
B
W
R
. Define F
∗
to be F
without the edges incident to v
∗
R
, and define F
∗
i
for
i =0, ,m analogously.
Write C
∗
0
= C(v
0
,F
∗
). For j ≥ 1, define inductively C
∗
j
to be the union of
all vertex components of F
∗
that are contained in, or adjacent to, C
∗
j−1
.
Let Q
∗
0
= C(v
0
,F
∗
0
). For j ≥ 1, define inductively Q
∗
j
to be the union of
all vertex components of F
∗
j
that intersect Q
∗
j−1
.
We show by induction on j that C
∗
j
stochastically dominates Q
∗
j
. The
induction base where j = 0 is obvious. For the inductive step, assume that
0 ≤ j<mand there is a coupling µ
j
of F
and (F
0
,F
1
, ,F
j
) such that
C
∗
j
⊃ Q
∗
j
holds µ
j
-a.s. Let H be a set of vertices in B
R
such that C
∗
j
= H
with positive probability. Let
H
c
denote the subgraph of B
W
R
spanned by
the vertices B
R
∪{v
∗
R
} H. Let S
H
be F
∩
H
c
conditioned on C
∗
j
= H.
Since C
∗
j
is a union of components of F
∗
, it is clear that S
H
has the same
distribution as a UST on
H
c
. Therefore, by the negative association property
of uniform spanning trees (see the discussion following Remark 5.7 in BLPS
[2]), S
H
stochastically dominates F
j+1
∩
H
c
(conditional on C
∗
j
= H). Hence,
Không có nhận xét nào:
Đăng nhận xét