A properly typeset version of this document is available in postscript and in pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
The loop-erased random walk is
the simple curve obtained by removing
in the chronological order the loops of the original random walk.
A basic aspect of these walks in Z^{2} is studied:
its average length (thus solving a conjecture of Guttmann).
The techniques are combinatorial and use a
bijection due to Temperley between maximal trees and perfect
coupling.
Figure 1: A random walk and its associated LERW
1 LERW=ST=DT
This is not a new equality between new complexity classes
but it simply emphasizes the fact that loop-erased random walk (LERW),
spanning tree (ST) and domino tiling (DT) are essentially the same object.
Indeed, in [12]
shows that, for a uniformly chosen spanning tree on a region of
Z^{2}, the unique arc (branch) between two points has the same
distribution as the LERW between these two points.
Moreover, Temperley [13] gives a constructive
one-to-one correspondence
between spanning trees and domino tilings.
From the other talk of Richard Kenyon, we know that
domino tiling (the so-called two dimensional lattice dimer model,
a model which has some ties with Ising model)
is the only nontypical ad hoc statistical physical model
where conformal invariance
is proved, so representations of the Virasoro algebra [15]
could help finding critical exponents.
In order to solve this ``self-avoiding walk model''
(i.e., to set the critical exponent),
R. Kenyon does not use representation theory,
but a ``discrete Laplacian'', from which he
gets the full asymptotics. Whereas a lot is known about properties
of the continuous Laplacian [5], works on the discrete
Laplacian are more recent [10].
As conjectured by Bursill and Guttmann [4],
the exponent for LERW is 5/4. Richard Kenyon proves this
by applying the ``equality'' LEWR=ST on the following theorem
Theorem 1
On the uniform spanning tree process on N×Z, the expected
number of vertices on the arc from (0,0) to ¥ which lie
within distance N of the origin is N^{5/4+o(1)}.
The next theorem is sometimes attributed to Kirschoff [11] and
proven in [1].
Theorem 2 [Matrix-tree Theorem]
For a graph G with set of vertices {v_{i}},
let
D:=
æ ç ç ç ç è
deg(v_{1})
0
0
0
· · ·
0
0
0
deg(v_{n})
ö ÷ ÷ ÷ ÷ ø
-Adj(G),
then the number of spanning trees of G is the product of
the nonzero eigenvalues of D divided by the size of G.
For an m× n rectangle, the number of spanning trees is thus
Õ
(j,k)¹ 0
j=0,..., m-1
k=0,..., n-1
æ ç ç è
4-2cos(
p k
n
)-2cos(
p j
m
)
ö ÷ ÷ ø
.
It is possible to extend this kind of result to a class of polygons
which are decomposable in rectangles, the so-called Temperleyan
polyominoes. (Triangulations are also a way, as there is a
determinant-like expression for triangles.)
Figure 2: A graph and its associated Temperleyan polyomino
The number of spanning trees of the graph is the number of domino tilings
of its Temperleyan polyomino.
Taking the log in the previous formula gives a special case
of the following theorem:
Theorem 3
Let UÌ R^{2} be a rectilinear polygon with V vertices. For each
e>0, let P_{e} be a Temperleyan polyomino in eZ^{2} approximating U in the natural sense (the corners of
p_{e} are converging to the corners of U). Let A_{e}
be the area and Perim_{e} be the perimeter of P_{e}.
Then the log of the number of domino tilings of P_{e} is
c_{0}A
e
e^{2}
+
c_{1}Perim
e
e
+O(log(e))
where c_{0}=G/p, G=1-1/3^{2}+1/5^{2}-··· is
Catalan's constant, c_{1}=G/2p+log((2)^{1/2} -1)/4.
According to the author, ``Part of the motivation for the above
theorem is to validate a certain
heuristic, which attempts
to explain how the presence of the boundary affects the long-range
structure of a random tiling. In particular it attempts to explain
how the boundary affects the densities of local configurations far
from the boundary [3]. This heuristic is called the `phason strain'
principle.
The heuristic is as follows: The boundary causes the average
height function of a tiling to deviate slightly from its
entropy-maximizing value of 0. At a point in the region
where the average height function has nonzero slope, the ``local''
entropy there is smaller than the maximal possible entropy, by an
amount proportional to the square of the gradient of the average
height function.
The system behaves in such a way as to maximise the total entropy
subject to the given boundary values of the height function, and the
resulting average height function is the function which minimises the
(integral of) the square gradient. That is, the average height function
is harmonic.''
Anyway an exact application of the phason strain principle gives in
fact slightly different asymptotics (from the one given in the theorem 3), so
this principle is not totally valid
here, but however it gives a good approximation.
2 Height Function
For a given tiling, the height function h
is easily defined [14] by bicolouring the Temperleyan polyomino
(there are no adjacent vertices of the same colour):
Figure 3: A Temperleyan polyomino and the bicoloured associated graph
then, for each oriented edge AB on the border of a domino,
h(A)-h(B):=
ì í î
+1
if the square on the left of AB is black,
-1
otherwise.
Note that, up to an arbitrary additive constant, the height of the
boundary is independent of the tiling.
For a smaller and smaller lattice (e.g., e Z^{2}), one can
approximate any domain U of C.
For a very fine lattice (in fact, taking the limit when
e® 0), one can study the probability of appearance in
the tiling of some patterns, their repartition in the tiling and
also how the shape of the boundary influences the tiling.
It appears that there are links with conformal theory, as
explained below.
Let P_{e} be a Temperleyan polyomino associated
to a rectilinear polygon U of C.
Now, let h_{e} be the average height function of P_{e},
that is the average height over all domino tilings of P_{e}
and then define
h(x):=
lim
e ® 0
h
e
(x
e
).
For xÎ ¶ U, h(x) is defined by continuity from values of
h in the interior.
The remarkable fact is that this limiting average height function h
can be expressed as
h(v)=
4
p
Á
ó õ
v
b_{0}
lim
z®
v
æ ç ç è
F_{+}(v,z)-
2
p(z-v)
ö ÷ ÷ ø
du=-
2
p
Á log Ã'(z),
where Ã is the
Weiertrass elliptic function and where F_{+}(u,z) du is a meromorphic 1-form,
thus allowing some links with conformal mapping theory.
We refer to ``Conformal invariance of domino
tiling'' (1997) and to ``The asymptotic determinant of the
discrete Laplacian'' (1999) for further informations^{1}.
Brooks (R. L.), Smith (C. A. B.), Stone (A. H.), and Tutte (W. T.). --
The dissection of rectangles into squares. Duke Mathematical
Journal, vol. 7, 1940, pp. 312--340.
Burton (Robert) and Pemantle (Robin). --
Local characteristics, entropy and limit theorems for spanning trees
and domino tilings via transfer-impedances. The Annals of Probability,
vol. 21, n°3, 1993, pp. 1329--1371.
Guttmann (A.) and Bursill (R.). --
Critical exponent for the loop-erased self-avoiding walk by
Monte-Carlo methods. Journal of Statistical Physics, vol. 59,
1990, pp. 1--9.
Kenyon (Richard). --
Local statistics of lattice dimers. Annales de l'Institut Henri
Poincaré. Probabilités et Statistiques, vol. 33, n°5,
1997, pp. 591--618.
Kirchhoff (G.). --
Über die Auflösung der Gleichungen, auf welche man bei der
Untersuchung der linearen Verteilung galvanischer Ströme geführt
wird. Annalen für der Physik und der Chemie, vol. 72,
1847, pp. 497--508.
Temperley (H. N. V.). --
Enumeration of graphs on a large periodic lattice. In Combinatorics. London Mathematical Society Lecture Note Series,
pp. 155--159. --
Cambridge University Press, 1974. Proceedings of the
British Combinatorial Conference, University College, Wales, Aberystwyth,
1973.