1. Random Walks on a Tree
A graph is defined as a pair (V, J5), where V is a set of vertices and E1 a family
of unordered pairs of vertices, called edges . A graph is said to be locally finite if
each element x of V belongs to finitely many edges. A tree is a graph with two
special properties: (1) it is connected and (2) it has no circuits. To define these
properties we must introduce the notion of chain: a chain is a finite sequence of
distinct vertices {xo,X\, ,x
} such that
E, for 1 j m. We
say that the graph is connected if given any two distinct vertices x and y there
exists a chain {xo,#i, *
#m} such that x = xo and y = xm. In this case we
also say that the chain joins x and y. The graph has no circuits if given two
vertices x and y there exists at most one chain joining x and y.
In this paper we are only concerned with locally finite homogeneous trees. A
tree is called homogeneous of degree d if each vertex belongs to exactly d edges.
For a locally finite tree, the degree must be a positive integer which we will
always denote by q-\-1. If q = 0, then the tree has two vertices; if q = 1, then the
tree is one doubly infinite chain of vertices. Figures la and lb show homogeneous
trees of degrees three and four.
The vertex set of any tree has a natural metric space structure. Let x, y G V
and let {x =
= y} be the unique chain joining x and y. Then
m is the distance between x and y denoted d(x,y). (Of course this definition
makes d(x,x) = 0.)
We shall be concerned with a certain group G whose Cayley graph is a tree.
If G is any group and #i, , xn a given set of generators, the Cayley graph of
G, with respect to these generators, has vertex set V equal to G and edge set
E = {{X,XXJ}; x £ G,j = 1, -n} .
Let G be the free product G = Z2 * * Z2 of q + 1 copies of Z2, and let
ai, , a
q +
i be the obvious generators of G, each one an involution generating
one copy of Z2. The Cayley graph of G with respect to these generators is a
homogeneous tree of degree q + 1. For q+ 1 = 3 this tree is represented by the
diagram of Figure la (where we denote ai, a2, as by a, 6, and c.)
Other groups also have Cayley graphs which are trees. For instance if G is a
free group on two generators a and b, then the Cayley graph of G with respect
to the generators a and b is a tree represented by the diagram of Figure lb. The
results and methods of this paper apply, in fact, to all groups having a Cayley
graph which is a homogeneous tree. However, for clarity we will consider only
the group G = Z2 * Z2.
Previous Page Next Page