Lamplighter groups, de Bruijn graphs, spider-web
graphs and their spectra

arXiv:1502.06722v3 [math.CO] 29 May 2017

R. Grigorchuk∗, P.-H. Leemann and T. Nagnibeda
May 30, 2017

Abstract
We study the infinite family of spider-web graphs {Sk,N,M }, k ≥ 2,
N ≥ 0 and M ≥ 1, initiated in the 50-s in the context of network theory.
It was later shown in physical literature that these graphs have remarkable
percolation and spectral properties. We provide a mathematical explanation of these properties by putting the spider-web graphs in the context
of group theory and algebraic graph theory. Namely, we realize them as
tensor products of the well-known de Bruijn graphs {Bk,N } with cyclic
graphs {CM } and show that these graphs are described by the action of
the lamplighter group Lk = Z/kZoZ on the infinite binary tree. Our main
result is the identification of the infinite limit of {Sk,N,M }, as N, M → ∞,
with the Cayley graph of the lamplighter group Lk which, in turn, is
one of the famous Diestel-Leader graphs DLk,k . As an application we
compute the spectra of all spider-web graphs and show their convergence
to the discrete spectral distribution associated with the Laplacian on the
lamplighter group.

Keywords: The limit of graphs, de Bruijn graphs, lamplighter groups, DiestelLeader graphs, spider-web graphs, spectra.

1

Introduction

Exchange of methods and ideas between physics and mathematics has a long
history and led to many spectacular results. Spectral theory is one of many
examples of such a fruitful interaction.
The goal of this paper is to show how group theory can be successfully
applied to explain and study some objects of interest in physics and in the
network theory, with emphasis on their spectral properties.
Spider-web networks were introduced by Ikeno in 1959 [13] in order to study
systems of telephone exchanges. They were later shown to enjoy interesting
properties in percolation, see [18], [19] and [20]. Our work stems from the paper [1] by Balram and Dhar where they are interested in the asymptotic properties of the sequence of spider-web graphs {Sk,N,M }, for k = 2. In particular,
they find, using an interesting approach based on symmetries, the spectra of
∗ The authors were supported by the Swiss National Science Foundation. R.G. was also
supported by NSF grant DMS-1207669

1

graphs S2,N,M and observe that they converge to a discrete limiting distribution as M, N → ∞.
Here, we develop a method that leads to the full understanding of this infinite
discrete model, including its spectral characteristics, via finite approximations,
using the notion of Benjamini-Schramm limit of graphs that has lately become
very important in probability theory. A remarkable feature of the model that we
discover is that it is related to one of the most interesting and important testcases in combinatorial group theory, both algebraically and from the spectral
and probabilistic viewpoints, the lamplighter groups.
It is interesting to observe that the study of more and more models in pure
and applied mathematics, theoretical and statistical physics and in computer
science see abstract groups appearing naturally, not only describing symmetries,
but also serving as non-commutative time scales in dynamical systems, describing monodromies, providing automatic structure etc. However, the work was
mostly done on the cubic lattices and the Bethe lattice and its close relatives
(as e.g. the modular group of the surface groups), in relation to percolation,
the Ising model, the sandpile model and many more. It is therefore particularly
interesting that, as we show, a lattice with very different geometry, the DiestelLeader graph associated to the lamplighter group, arises naturally as the limit
of the spider-web graphs. The explicit identification, presented here, of this
infinite lattice as the limit of spider-web graphs, leads immediately to spectral
results, but also potentially to future advancements in the study of percolation
on these graphs, as explained in [20].
The aim of the present paper is therefore to provide a unified rigorous framework for studying spider-web graphs S2,N,M , for any k ≥ 2, and their spectra,
and to identify their limit, as M, N → ∞, as a particular Cayley graph of the
lamplighter group Lk = Z/kZ o Z (see Subsection 3.4 for the definition) known
(see [24]) as the Diestel-Leader graph .
Convergence of spider-web graphs to this graph comes from the following
structural result that we prove. For any k ≥ 2, the oriented spider-web graph
S~k,N,M decomposes into the tensor product of the graph S~k,N,1 and the oriented
~ M of length M . It is then useful to note that the sequence S~k,N,1 is nothcycle C
ing else than the well-studied sequence of de Bruijn graphs, see Subsection 4.1.
De Bruijn graphs are famous for their useful connectivity properties and, being
both Hamiltonian and Eulerian, are used both in mathematics, where they represent word overlaps in symbolic dynamical systems, and in applications, as for
example for the discrete model for the Bernoulli map or for genome assembly
in bioinformatics [4]. Our results imply that, for each k ≥ 2, the two-parameter
family {Sk,N,M } of spider-web graphs is in fact a natural extension of the family
of de Bruijn graphs Bk,N .
We then prove a result of independent interest, that de Bruijn graphs are
isomorphic to another well-known sequence of finite graphs provided by a selfsimilar action of the lamplighter group Lk by automorphisms on the k-regular
rooted tree, see [12]. Our main result then follows: the sequence of spider-web
graphs S~k,N,M (respectively Sk,N,M ) converges, as M, N → ∞ to the Cayley graph of the lamplighter group Lk , see Theorem 4.4.2 (respectively Corollary 4.4.2). There is also an alternative more direct way to prove that de Bruijn
graphs Bk,N (as well as the spider-web graphs) converge to the Diestel-Leader
graph DL(k, k) [16].

2

The spectra of de Bruijn graphs have been computed by Delorme and Tillich
in [5]. We extend this computation to all spider-web graphs by using their tensor
product structure. The spectral approximation in the context of BenjaminiSchramm limits (see Definition 2.4) then ensures that the spectra of finite spiderweb graphs converge to the spectral distribution corresponding to the limit
graph. As mentioned above, this spectral distribution coincides with one of
those associated with the lamplighter group.
The spectral theory of discrete Laplacians on lattices and on Cayley graphs
is a very popular topic related to the theory of random walks on groups initiated
by Kesten, Atiyah’s theory of L2 -invariants, Kadison-Kaplansky Conjecture and
many more. It can be viewed as a discrete analogue of the famous Kac’s question
“Can one hear the shape of a drum”. The lamplighter group is a very interesting
object from the viewpoint of spectral theory. It was open for a longtime whether
the Laplacian spectrum on a Cayley graph can have a discrete component. This
was answered in [12] where it was shown that the spectrum of a certain Cayley
graph of the lamplighter group is pure point.
On the other hand, it follows from [7] by Elek that for the “standard” generating set (the one that corresponds to the algebraic structure of the lamplighter
group), the spectrum contains no eigenvalue. This is illustrated on Figure 1,
where the left column corresponds to the Diestel-Leader graph DL(2, 2) which,
as we have already mentioned, is isomorphic to a specific Cayley graph of L2 ,
see (‡) on page 14, whereas the right column corresponds to the Cayley graph
of L2 with respect to the standard generating set (see (†) on page 14).
This is the first example of a dramatic change that the Laplacian spectrum
can undergo under local perturbations, even in the presence of a large underlying
group of symmetries. Recently other examples of this type were discovered by
the first and the third authors in collaboration with Lenz [8, 9], in the context
of group actions with aperiodic order.
The first two lines of Figure 1 are the histograms of the spectral measure
(respectively for linear and logarithmic y-axes) and the last line shows the corresponding density functions. In both cases the graphics correspond to approximations of the infinite graph by graphs with 2N vertices (provided by the action
of L2 on the infinite full binary tree, see Subsection 4.3). On the left, the DiestelLeader graph is approximated by de Bruijn (and equivalently spider-web S2,N,M
for any M ) graphs (see Remark 5.1); in this case the exact spectral measure is
known ([12], see also (#) on page 29). It is not known for the Cayley graph of
Lk with respect to the standard generators.
The paper is organized as follows. Section 2 introduces all the relevant
notions from graph theory and contains some useful preliminary results. In
particular, we recall the notion of the topological space of marked graphs. We
then turn our attention to the study of tensor product of graphs in Section 3.
In Subsection 3.1 we investigate how the tensor product behaves under the
convergence in the space of marked graphs. Starting from Subsection 3.3 we
specialize to the case of graphs defined by a group action (so called Schreier
graphs, see definition 3.3.1), and further to the case of the lamplighter group
in Subsection 3.4. The structure of spider-web graphs is analyzed in Section 4.
Subsection 4.4 establishes in particular a connection between spider-web graphs
and lamplighter groups. Section 5 contains spectral computations on spider-web
graphs. In the last Section 6 we provide some further results about spider-web
graphs and their relation to lamplighters. It turns out that all S~k,N,M are
3

0.3

0.2

0.2

0.1

0.1

0
0

10

Linear axis

0.3

0
−4 −3 −2 −1

0

1

2

3

4
100

10−1

10−1

10−2

10−2

10−3

10−3

−4 −3 −2 −1

Density function

Standard generators

0

1

2

3

4

1

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

−3

−2

−1

0

1

2

3

−3

−2

−1

0

1

2

3

−3

−2

−1

0

1

2

3

Logarithmic axis

Spectral measure

de Bruijn graph

0
−4 −3 −2 −1

0

1

2

3

4

Figure 1: Approximations of the spectral measure and of the density function
of two Cayley graphs of the lamplighter group L2 . The standard one on the right
(see Subsection 3.4), and the Diestel-Leader graph DL(2, 2) approximated by
de Bruijn (and spider-web S2,N,M , any M ) graphs on the left. The histograms
correspond to graphs with 2N , N = 10, vertices.

4

Schreier graphs of the lamplighter group Lk (Theorem 4.4.1) and we identify
the subgroups to which they correspond (Theorems 4.4.1 and 6.1.2). It is then
shown in Theorem 6.2.1 that for all k, the graph S~k,N,M is transitive if and only
if M ≥ N . In Theorem 6.1.3, we show that if moreover N divides M , it is a
Cayley graph of a finite quotient of the lamplighter group Lk .
The authors would like to thank Vadim Kaimanovich for his interest in this
work and for inspiring discussions on the subject of the paper. They also would
like to thank the anonymous referee for his careful reading and his valuable
remarks.

2

Definitions and preliminaries

In this paper we deal with both oriented and non-oriented graphs and allow loops
and multiple edges. It will be convenient for us to work with the definition of a
graph suggested by Serre [22].
Definition 2.1. A (non-oriented) graph Γ = (V, E) consists of two disjoint sets
V (vertices) and E (oriented edges), and three functions ι, τ : E → V (initial
vertex and end vertex) and ¯: E → E (the inverse edge) satisfying ι(ē) = τ (e),
ē¯ = e and ē 6= e. A non-oriented edge is a pair {e, ē}.
~ is given by a set of vertices V , a set of oriented
An oriented graph ~Γ = (V, E)
edges E and two functions ι, τ : E → V with no conditions on them. To avoid
confusion, from now on we will always write graph for non-oriented graph and
oriented graph otherwise.
An orientation O on a graph Γ is the choice of an edge in each of the pairs
{e, ē}. For each choice of an orientation O on Γ = (V, E), we define the oriented
~ where E
~ = O and ι and τ are restrictions on E
~ of the original
graph ~Γ = (V, E)
functions.
~ is the graph ~Γ(V, E),
The underlying graph of an oriented graph ~Γ = (V, E)
~
~
with E := E t {ē | e ∈ E}, where ē is the formal inverse of e. For ē, we define
ι(ē) := τ (e), τ (ē) := ι(e) and ē¯ := e.
The operations of choosing an orientation on a graph and of taking the
underlying graph of an oriented graph are mutually inverse in the following
sense. Given a graph Γ, the underlying graph of the oriented graph obtained
by choosing an orientation on Γ, is Γ itself. On the other hand, given an
oriented graph ~Γ there exists an orientation on the underlying graph such that
the resulting oriented graph is ~Γ itself.
Remark 2.1. In this paper we will only consider connectedness in the weak
(non-oriented) sense. In particular, a connected component of ~Γ is a connected
component of ~Γ with the orientation coming from ~Γ.
Let Γ = (V, E) be a graph, oriented or not. The in-degree, respectively the
out-degree, of a vertex v is the number of edges e with initial vertex v, respectively end vertex v. If the graph is non-oriented, then both notions coincide and
are simply called degree. The graph Γ is said to be locally finite if every vertex
has both finite in-degree and finite out-degree. Note that if e is a loop in a
graph, it contributes 1 to the in-degree, but its inverse edge ē also contributes 1.
Therefore, the non-oriented loop {e, ē} contributes 2 to the degree, since ē 6= e.
5

The adjacency matrix of graph Γ is the symmetric matrix AΓ = (aij )i,j∈V
with aij the number of edges from i to j. For an oriented graph ~Γ the adjacency
matrix is not necessary symmetric, but we have: A~Γ = A~Γ + A~TΓ .
~ 1 → V2 ∪
A morphism of oriented graphs ~Γ1 → ~Γ2 is a function φ : V1 ∪ E
~
~
~
E2 such
 that φ(V1 ) ⊆ V2 , φ(E
 1 ) ⊆ E2 and
 for every edge e in Γ1 , we have
ι φ(e) = φ ι(e) and τ φ(e) = φ τ (e) . A morphism of graphs is defined
in the same way, with the additional requirement that φ(e) = φ(ē). Let ∆ be
a graph (oriented or not) and let v any vertex of ∆. The star of v is the set
{e ∈ E | ι(e) = v}. Remark that any morphism φ : ∆1 → ∆2 induces, for any
vertex v of ∆1 , a map: φv : Starv → Starφ(v) . A morphism φ : ∆1 → ∆2 is a
covering if all the induced maps φv are bijections. In this case, we say that ∆1
covers ∆2 .
Let Γ be a graph. A path p in Γ from v to w is an ordered sequence of
edges (e1 , e2 , . . . , en ) such that ι(e1 ) = v, τ (en ) = w and for all 1 ≤ i < n we
have τ (ei ) = ι(ei+1 ). The inverse of the path p = (e1 , e2 , . . . , en ) is the path
p̄ = (ēn , . . . , ē1 ). The length of a path (e1 , e2 , . . . , en ) is equal to n. A path is
said to be reduced if it does not contain subsequences of the form eē.
Definition 2.2. Let Γ be a non-oriented graph, p = (e1 , . . . , en ) a path of
length n in Γ and O an orientation on Γ. The signature σ(p) of p with respect
to O is an ordered sequence of ±1 of length n, where there is a 1 in the position
i if and only if ei belongs to O and a −1 otherwise.
The derangement of p with respect to O, der(p), is the sum of the ±1 in the
signature of p. The derangement of a path of length 0 is 0. It follows from the
definition that der(p̄) = − der(p) and that σ(p̄) is the sequence −σ(p) readed
backward.
The derangement of Γ with respect to O is
der(Γ) := min{|der(p)| | p is a closed path in Γ and der(p) 6= 0},
where this minimum is defined to be 0 if there is no closed path in Γ with
non-zero derangement.
~
We also need a variant of this definition for an oriented graph ~Γ = (V, E)
and p a path in the underlying graph. The signature of p, respectively the
derangement of p, are the signature, respectively the derangement, of p with
respect to the orientation coming from ~Γ. The derangement of ~Γ is der(~Γ) :=
der(~Γ), for the orientation on ~Γ coming from ~Γ.
Definition 2.3. A marked graph is a couple (Γ, v) where Γ is a graph and v
a vertex of Γ, called the root of the marked graph. For an (oriented) marked
graph (Γ, v) we will denote by (Γ, v)0 the connected component containing v.
We denote G∗ (respectively G~∗ ) the set of connected marked (respectively
connected oriented marked) graphs, up to isomorphisms of marked graphs.
The set G∗ (respectively G~∗ ) can betopologized by considering for example
1
the following distance: d (Γ, v), (∆, w) = 1+r
, where r is the biggest integer
such that the ball of radius r centered at v in Γ and the ball of the same radius
centered at w in ∆ are isomorphic as marked (respectively marked oriented)
graphs. If the two graphs are isomorphic as marked graphs, then the distance
is defined to be 0. For an oriented marked graph (~Γ, v), the ball of radius r
6

centered at v is the oriented subgraph of ~Γ such that its underlying graph is
the ball of radius r centered at v in ~Γ. For any integer d, the subspaces G∗,≤d
of G∗ and G~∗,≤d of G~∗ consisting of graphs with both maximal in-degree and
out-degree bounded by d are compact.
~ w) are two oriented marked graphs,
It is easy to check that, if (~Γ, v) and (∆,
then


~ w) .
~ w) ≥ dG (~Γ, v), (∆,
dG~∗ (~Γ, v), (∆,
∗
It immediately implies the following proposition.

Proposition 2.1. If a sequence of oriented marked graphs (~Γn , vn ) converges
to (~Γ, v), then the sequence (~Γn , vn ) converges to (~Γ, v).
Since G∗,≤d is a metric space which is separable, compact and complete,
by Prokhorov’s Theorem [21] the space of Borel probability measures on it
is compact in the weak topology. There is a natural way to attach a Borel
probability measure to a finite graph Γ: by choosing theProot uniformly at
random. More formally, the measure associated to Γ is |V1 | v∈V δ(Γ,v)0 , where
δ is a Dirac measure.
Definition 2.4 ([3]). Let Γn be a sequence of finite graphs and let λΓn be the
Borel probability measures associated. We say that Γn is Benjamini-Schramm
convergent with limit λ if λΓn converges to λ in the weak topology in the space
of Borel probability measures on G∗ .
In the particular case where λ is a Dirac measure concentrated on one transitive graph Γ, we say that Γn converges to Γ in the sense of Benjamini-Schramm.
The same definitions hold in G~∗ . In this paper we will deal with Schreier
graphs coming from group actions, so we also need to establish a similar setup
for labeled graphs.

~
Definition 2.5. An oriented labeled graph is a triple ~Γ, X, l , where ~Γ = (V, E)
~
is an oriented graph, X an alphabet (the set of labels) and l : E → X a function
(the labeling). The underlying labeled graph is (~Γ, X, l0 ) where l0 : E → X t X −1
~ we have l0 (e) := l(e) and l0 (ē) := l(e)−1 . A
such that for every edge e in E
morphism of (oriented) labeled graphs over the same alphabet which preserves
the labeling is called a strong morphism. If we forget about the labeling and the
morphism is only between (oriented) graphs, we say the this is a weak morphism.
Typical examples of labeled graphs are Cayley graphs and more generally
Schreier graphs, see Definition 3.3.1.
Every concept that can be expressed using morphisms in the category of
(oriented) graphs has an obvious “strong” analog in the category of (oriented)
labeled graph with strong morphisms. Thus, we have strong isomorphisms,
strong coverings, a distance in the space of marked labeled graphs and hence a
notion of strong convergence and of strong Benjamini-Schramm convergence.

3

Tensor product of graphs

Definition 3.1. Let Γ = (V, E) and ∆ = (W, F ) be two (oriented) graphs.
Their tensor product is the (oriented) graph Γ ⊗ ∆, with vertex set V × W ,
7

where there is an edge (e, f ) from (v1 , w1 ) to (v2 , w2 ) if e is an edge from v1 to
~ If Γ = (V, E) and ∆ = (W, F ) are
v2 in ~Γ and f is an edge from w1 to w2 in ∆.
non-oriented graphs, then the inverse of the edge (e, f ) is the edge (ē, f¯).
If Γ = (V, E) has labeling l : E → X and ∆ = (W, F ) has labeling l0 : F → Y ,
the tensor product has labeling l × l0 : E × F → X × Y .

~ and ~Γ we have ~Γ ⊗ ∆
~ '∆
~ ⊗ ~Γ and ∆
~ ⊗ ∅ ' ∅,
For two oriented graphs ∆
where ∅ denotes the empty graph.
The tensor product of (oriented) graphs is the categorical product in the
category of (oriented) graphs. This implies that for any pair of morphisms
~ and φ0 : ~Γ0 → ∆
~ 0 , φ ⊗ φ0 is a morphism from ~Γ ⊗ ~Γ0 to ∆
~ ⊗∆
~ 0 and
φ : ~Γ → ∆
0
0
that φ ⊗ φ is an isomorphism if and only if φ and φ are isomorphisms.
Lemma 3.1. For i = 1, 2, let φi : Γi → ∆i be a covering. Then, φ1 ⊗ φ2 : Γ1 ⊗
Γ2 → ∆1 ⊗ ∆2 is a covering. The same result is true for oriented graphs.

Proof. Let (v1 , v2 ) be any vertex in Γ1 ⊗ Γ2 . Since the φi ’s are coverings, the
induced morphisms (φi )vi : Starvi → Starφi (vi ) are bijections. On the other
hand, by definition of the tensor product, there is a natural bijection between
Starv1 × Starv2 and Star(v1 ,v2 ) . Under this bijection, the map (φ1 ⊗ φ2 )(v1 ,v2 )
corresponds to (φ1 )v1 × (φ2 )v2 and is therefore a bijection.
~ be an oriented graph. The line graph of ~Γ is
Definition 3.2. Let ~Γ = (V, E)
~ (the edge set of ~Γ) and with an edge
the oriented graph L(~Γ) with vertex set E
from e to f if we have τ (e) = ι(f ) (that is f “directly follows” e) in ~Γ .
~ i ) be an oriented graph. Then the
Lemma 3.2. For i = 1, 2, let ~Γi = (Vi , E
~
~
~
~
graphs L(Γ1 ) ⊗ L(Γ2 ) and L(Γ1 ⊗ Γ2 ) are isomorphic.

Proof. Vertices of L(~Γ1 ⊗ ~Γ2 ) are in 1-to-1 correspondance with edges of ~Γ1 ⊗ ~Γ2
~1 × E
~ 2 . On
and therefore in 1-to-1 correspondance with pairs of edges in E
~
~
the other hand, vertices of L(Γ1 ) ⊗ L(Γ2 ) are in 1-to-1 correspondance with
{(v1 , v2 ) | vi a vertex in L(~Γi )}. Therefore, vertices of L(~Γ1 ) ⊗ L(~Γ2 ) are also in
~1 × E
~ 2.
1-to-1 correspondance with pairs of edges in E
Now, in L(~Γ1 ⊗ ~Γ2 ) there is an edge from (e1 , e2 ) to (f1 , f2 ) if and only if, for
i = 1, 2, fi directly follows ei in Γi . The same relation holds in L(~Γ1 ) ⊗ L(~Γ2 ),
which proves the isomorphism.

3.1

Tensor product and convergence

Recall that for a marked labeled graph (~Γ, v), we denote by (~Γ, v)0 the connected
component of ~Γ containing the root, with the orientation coming from ~Γ.
~ m , ym ) converges
Theorem 3.1.1. If (~Γn , vn ) converges (in G~∗ ) to (~Γ, v) and (Θ
~
to (Θ, y) then the following diagram is commutative

~Γn ⊗ Θ
~ m , (vn , ym ) 0
m

∞

n

m

n,m
∞

∞


~Γn ⊗ Θ,
~ (vn , y) 0


~Γ ⊗ Θ
~ m , (v, ym ) 0
∞

∞

n

8


~Γ ⊗ Θ,
~ (v, y) 0

Proof. Take any  > 0. By convergence, there exists n0 and m0 such that for
every n ≥ n0 the graphs (~Γn , vn ) and (~Γ, v) are at distance lesser than  and
~ m , vm ) and (Θ,
~ v) are too at distance
such that for every m ≥ m0 the graphs (Θ
lesser than .
~ 1 , v), (∆
~ 2 , w), (Π
~ 1 , x) and (Π
~ 2 , y) be four elements of G~∗ . We afLet (∆


~1 ⊗ Π
~ 1 , (v, x) 0 and ∆
~2 ⊗ Π
~ 2 , (w, y) 0 is
firm that the distance between ∆


~ 1 , v), (∆
~ 2 , w) and d (Π
~ 1 , x), (Π
~ 2 , y) .
lesser or equal to the maximum of d (∆
0
0
~ m , (vn , ym ) and ~Γ⊗ Θ,
~ (v, y)
Lemma 3.1.1 below implies in turn that ~Γn ⊗ Θ
are at distance less than , which proves the convergence when both n and m
grow together.
~ m constant
Now, if we take first the limit on n we can use this result with Θ
to find

 

~Γn ⊗ Θ
~ m , (vn , ym ) 0 = ~Γ ⊗ Θ
~ m , (v, ym ) 0 .
lim
n→∞

Taking then the limit on m (with ~Γ constant) we have that the upper right
triangle is commutative. A similar argument proves the commutativity of the
downer left triangle.

Note that Theorem 3.1.1 holds also for non-oriented marked graphs as well
as for labeled marked graphs with strong morphisms.
We will now prove the technical result used in the proof of Theorem 3.1.1.
~ be two oriented graphs and p be a path in ~Γ ⊗ ∆
~
Lemma 3.1.1. Let ~Γ and ∆
~
~
from (x, v) to (y, w). Then there exists paths q in Γ from x to y and r in ∆
from v to w with same signature as p.
More precisely, given a non-negative integer n and a sequence σ of ±1 of
length n, there is a bijection between the set of paths p from (x, v) to (y, w) in
~Γ ⊗ ∆
~ of signature σ and the set of couples (q, r) where q is a path in ~Γ from x
~ from v to w, both of signature σ.
to y and r a path in ∆
Proof. It is obvious that the second statement implies the first one. By definition
of the tensor product, we have a function φ from the set of paths from (x, v)
to (y, w) to the set of couples (q, r) where q is a path in ~Γ from x to y and
~ from v to w. Indeed, φ is the product of the left projection
r a path in ∆
and the right projection. This function naturally preserves the signature and is
injective. Now, if q = (e1 , . . . , en ) and r = (e01 , . . . , e0n ) have the same signature
~ in which case we have an
σ then either e1 belongs to ~Γ and e01 belongs to ∆,
0
0
~ or ē1 belongs to ~Γ and ē belongs to ∆,
~ in which case we
edge (e1 , e1 ) in ~Γ ⊗ ∆,
1
0
~
~
have an edge (ē1 , ē1 ) in Γ ⊗ ∆. By induction, it is possible to construct a path
~ from (x, v) to (y, w) with signature σ.
p in ~Γ ⊗ ∆

3.2

Tensor product with an oriented cycle and the oriented line

Let us first consider the special case when one of the factors in the tensor
~ ∞ or C
~ M , where C
~ ∞ is the “oriented line” with V ~ = Z (the
product is C
C∞
set of integers) and for each vertex i there is a unique oriented edge from i to
~ M is the “oriented cycle of length M ”: V ~ = Z/M Z and for each i
i + 1, and C
CM

9

there is a unique oriented edge from i to i + 1 modulo M . Below, we will write
M ∈ N = {1, 2, . . . , ∞} and i ≡ j (mod ∞) will mean i = j.
In this subsection we will only consider oriented connected graphs ~Γ. Recall
the notion of derangement of a path from Definition 2.2 that we will need here.
Proposition 3.2.1. For any oriented connected graph ~Γ and any M ∈ N, all
~ M are isomorphic.
connected components of ~Γ ⊗ C
Proof. Fix a vertex v of ~Γ. Since ~Γ is connected, for any vertex w there is a path
q from v to w in ~Γ, with signature σ(q). For any integer i, there exists a path
~ M with signature σ(q) = σ(r). Therefore,
r from i to i + der(q) (mod M ) in C

~ M from (v, i) to w, i + der(q) . Hence, for any vertex
there is a path p in ~Γ ⊗ C
~ M , there exists an integer i such that (w, j) is in the connected
(w, j) in ~Γ ⊗ C
component of (v, i).
~ M , i)
On the other hand, since for any integers i and j, the marked graphs (C
~
and (CM , j) are isomorphic, say by an isomorphism φi,j , we have connected


~ M , (v, i) 0 and ~Γ ⊗ C
~ M , (v, j) 0 are isomorphic by Id ⊗φi,j .
components ~Γ ⊗ C
This implies that all connected components are isomorphic.
Theorem 3.2.1. Let ~Γ be a connected locally finite oriented graph. For any
M ∈ N and any vertex v in ~Γ, the marked oriented graph (~Γ, v) is isomorphic (as

~ M , (v, 0) 0 if and only if der(~Γ) ≡ 0 (mod M ).
marked oriented graph) to ~Γ ⊗ C

Proof. Suppose that der(~Γ) ≡ 0 (mod M ). For any vertex w of ~Γ define rk(w),
the rank of w, to be the derangement of any path in ~Γ from v to w taken modulo
M . This is well defined since for two such paths p and q, the concatenated
path pq̄ is a closed path based at v with derangement 0 (mod M ). We define


~ M , (v, 0) 0 by w 7→ w, rk(w) for vertices.
a morphism from (~Γ, v) to ~Γ ⊗ C

For the edges,
it maps an edge e from w to x to an edge

 from w, rk(w) to
x, rk(x) . Note that the vertices w, rk(w) and x, rk(x) are indeed connected
by an edge in the tensor product since rk(x) = rk(w) + 1. It is easy to see that
this morphism is surjective and injective, and hence is an isomorphism.
Suppose now that der(~Γ) 6≡ 0 (mod M ). This implies the existence of a
closed path q0 in ~Γ from v to v with non-zero (mod M ) derangement and
length n. By the second part of Lemma 3.1.1, the set of closed paths q based at
v and of length n is in bijection
with the set of (non necessarily closed) paths

p from (v, 0) to v, der(q) , where we used the fact that for every signature σ,
there is a unique path in CM with initial vertex 0 and signature σ. Hence, the
~ M of length n based at (v, 0) is at most the
number of closed paths in ~Γ ⊗ C
number of closed path of length n based at v, minus one (namely the path q0 ).
If ~Γ is locally finite (note that local finiteness of ~Γ is used only in this direction
of the proof), there is only a finite number of such paths. In this case, (~Γ, v)

~ M , (v, 0) 0 cannot be isomorphic (as oriented marked graphs).
and ~Γ ⊗ C
Remark 3.2.1. Proposition 3.2.1 and Theorem 3.2.1 (and their proofs) are still
true in the category of labeled oriented graphs (with strong morphisms) if we
identify the labeling (l × l0 ) of the tensor product with its first coordinate l,
which is the labeling of ~Γ. In the following, we will always use this identification
~M .
for tensor product of the form ~Γ ⊗ C
10

We know by Proposition 3.2.1 and Theorem 3.2.1 that all connected com~ M are isomorphic and we are able, in the locally finite case,
ponents of ~Γ ⊗ C
to decide when they are isomorphic (as marked graphs) to ~Γ. To complete the
~ M it remains to count the number of connected components.
description of ~Γ ⊗ C
This is the subject of the next proposition.
Proposition 3.2.2. For any connected oriented graph ~Γ, and any M ∈ N and
any i ∈ Z, let [i] denotes the unique representative of i modulo M such that
−M/2 < [i] ≤ M/2. For M = ∞, we define [i] := i. For any connected graph
~Γ, the number of connected components of ~Γ⊗ C
~ M is M if and only if der(~Γ) ≡ 0
(mod M ). Otherwise it is equal to the absolute value of [der(~Γ)].
~ is infinite if
In particular, the number of connected component of ~Γ ⊗ Z
~
~
der(Γ) = 0 and der(Γ) otherwise.
Proof. Choose a vertex v0 in ~Γ. For every vertex w of ~Γ there is a path q in
~Γ from w to v0 , of length n and signature σ. For any i there is obviously a
~
path r in CM of length n and signature σ with initial vertex [i] and end vertex
i + der(r) . Hence, for every vertex (w, [i]) of the tensor product, there is a

~ M . Therefore, to count the
path p from (w, [i]) to v0 , [i + der(r) ] in ~Γ ⊗ C
~
~
number of connected components of Γ ⊗ CM it is sufficient to know when two
vertices (v0 , [i]) and (v0 , [k]) are connected. But they are connected if and only
if (v0 , [0]) and (v0 , [k − i]) are connected.
Let i0 be the non-zero integer with the smallest absolute value such that
~ M . If such an integer does
(v0 , 0) and (v0 , [i0 ]) are connected by a path in ~Γ ⊗ C
not exist, put i0 = M . The previous discussion implies that i0 = M if and only
~ M is M . On the other hand,
if the number of connected components of ~Γ ⊗ C
~
~
i0 = M if and only if every path p in Γ ⊗ CM with initial vertex (v0 , 0) and end
vertex (v0 , j) satisfies j = 0, in which case der(p) ≡ 0 (mod M ). But this is
~ M of a path with arbitrary
equivalent (by Lemma 3.1.1 and by the existence in C
signature) to every closed path q in ~Γ with initial vertex v0 having der(q) ≡ 0
(mod M ), which is equivalent to der(~Γ) ≡ 0 (mod M ).
If i0 6= M , we have either M = ∞ or M/2 < i0 ≤ M/2. In both cases
i0 = [i0 ]. For every integer
j, since (v0 , 0) and (v0 , i0 ) are connected, their

images (v0 , [j]) and (v0 , [j]+i0 ) by the automorphism Id ⊗φ0,[j] are connected,
~ M sending i on i + [j]. Hence the vertices
where
of C
 φ0,[j] is the automorphism

(v0 , [j] − i0 ) and (v0 , [j] − i0 + i0 ) are also connected. As a special case we
have that (v0 , 0) and (v0 , [−i0 ]) are connected. Therefore we can suppose that
i0 is strictly positive and 0 < i0 ≤ M/2. We also have by induction that for
all j, (v0 , [j]) is connected to (v0 , k) for some 0 ≤ k ≤ i0 . On the other hand,
(v0 , 0), (v0 , 1), . . . and (v0 , i0 − 1) are in different connected components by
~ M is i0 .
minimality of i0 . Hence, the number of connected components of ~Γ ⊗ C
~
Let us now show that i0 is equal to the absolute value of [der(Γ)]. Take a path
q in ~Γ with initial vertex v0 and such that |der(q)| = der(~Γ). By Lemma 3.1.1
~ M with der(p) = der(~Γ), initial vertex (v0 , 0) and end
this gives a path p in ~Γ ⊗ C
vertex (v0 , [der(p)]). This implies (by minimality of i0 ) that the absolute value
of [der(~Γ)] is bigger or equal to i0 , which is the number of connected components
of ~Γ.
It remains to show that i0 is bigger or equal to the absolute value of [der(~Γ)].
Now, if (v0 , 0) is connected by p to (v0 , i0 ), the derangement of p is equal to i0
11

modulo M . This gives us a closed path q (from v0 to v0 ) in ~Γ with derangement
i0 + aM for some integer a. Since [i0 + aM ] = [i0 ] = i0 , we have found a path q
in ~Γ such that [der(q)] = i0 . On the other hand, we have der(~Γ) ≥ |der(q)|. We
still have to show that |der(q)| ≥ [der(q)]. But the stronger inequality |i| ≥ |[i]|
is true for every integer i. Indeed, if −M/2 < i ≤ M/2 we have i = [i] and
therefore |i| = |[i]|. Otherwise, |i| > M/2 ≥ |[i]|.
An analogous proposition holds for non-oriented graphs, where the derangement is replaced by the length of a path and minimum is replaced by greatest
common divisor. This gives a refinement of the following proposition: Γ ⊗ ∆
is connected if and only if Γ and ∆ are connected and at least one factor is
non-bipartite ([14], Theorem 5.29).

3.3

Tensor product of a Schreier graph and an oriented
cycle

~ M , M ∈ N = {1, 2, . . . , ∞}, as one factor of the tensor product
Here we keep C
and take the other one to be as follows.
Definition 3.3.1. Let G be a group with a finite generating set X. The oriented
~
(right) Cayley graph Cay(G,
X) is the oriented marked labeled graph with vertex
set G and with an oriented edge from g to h labeled x if and only if h = gx,
x ∈ X. The standard choice for the root is 1G .
For H ≤ G, a subgroup, we define the oriented (right) Schreier graph
~
Sch(G,
H, X) to be the oriented marked labeled graph with vertex set {Hg |
g ∈ G} (the set of right H-cosets) and an edge with label x from Hg to Hh if
and only if Hh = Hgx. Here the standard choice of the root is (the coset) H.
If G acts on the right on a set V , we can define the graph of the action with
respect to the generating set X as the oriented labeled graph with vertex set
V and an edge from v to w labeled by x for every generator x ∈ X such that
v.x = w.
For every vertex v in V , the connected component of the graph of the action
with root v is strongly isomorphic (as marked labeled oriented graph) to the
~
Schreier graph Sch(G,
StabG (v), X).
~
Observe that for any vertices v and w in ~Γ = Cay(G,
X), the oriented labeled
~
~
~
marked graphs (Γ, v) and (Γ, w) are strongly isomorphic and thus Cay(G,
X)
is strongly vertex-transitive. This is not correct for Schreier graphs. Indeed,
~
Sch(G,
H, X) is in general not even weakly vertex-transitive.
Remark 3.3.1. For a generating set X of G, we can look at its symmetrization
X ± := {x | x ∈ X or x−1 ∈ X}. This is also a generating set of G. If e is the
~
unique edge in Cay(G,
X) with initial vertex g ∈ G and label x ∈ X ± , define ē
to be the unique edge with initial vertex gx and label x−1 . It is easy to see that
~
this operator ¯ makes of the oriented graph Cay(G,
X ± ) a non-oriented graph,
but with the possibility that ē = e. We will note this graph Cay(G, X). An
important fact for us is that there is a strong isomorphism between Cay(G, X ± )
~
and Cay(G,
X) if and only if there is no x ∈ X such that x2 = 1. Moreover,
in this case Cay(G, X ± ) is a graph in the sense of Definition 2.1 (i.e. there is
no e such that e = ē). Indeed, x2 = 1 if and only if x−1 = x. If x2 = 1, then
12

for every vertex v in Cay(G, X), the edge with initial vertex v and label x is
~
equal to the edge with initial vertex v and label x−1 , but in Cay(G,
X) they are
distinct by definition. If there is no such x, the strong isomorphism is trivial.
The same observation also applies to Schreier graphs.
Definition 3.3.2. Let w be a word in the alphabet X t X −1 . For x ∈ X, the
exponent of x in w, expx (w) is the number of times x appears in w minus the
number of times x−1 appears in w. We also define the exponent of X as the
sum of exponents:
X
expX (w) :=
expx (w).
x∈X

The definition immediately implies
Lemma 3.3.1. Let G = hX | Ri be a group presentation. Then the derange~
ment of a path in Cay(G,
X) is exactly the exponent of its label.
Proposition 3.3.1. Fix M ∈ N and let G = hX | Ri be a group presentation
~
such that expX (r) ≡ 0 (mod M ) for every relator r ∈ R. Then Cay(G,
X) is
~
~
strongly isomorphic to any connected component of Cay(G, X) ⊗ CM .
Proof. Let p be a path with initial vertex 1 in Cay(G, X) and let w be its label.
ThenQw = 1 in G if and only if p is closed. But w = 1 in G if and only if
−1
w = hi ri h−1
.
i , where the ri are relators and the hi are words in X t X
On the other hand, by the previous lemma the derangement of p is equal to
Y
expX (w) = expX ( hi ri h−1
i )
X

=
expX (hi ) + expX (ri ) − expX (hi )
≡0

(mod M ).

We conclude using Theorem 3.2.1 and Remark 3.2.1.
Lemma 3.3.2. Fix M ∈ N and let G = hX | Ri be a group presentation such
that expX (r) ≡ 0 (mod M ) for every relator r ∈ R. An oriented labeled graph
~Γ is the graph of an action of G if and only if ~Γ ⊗ C
~ M is also the graph of an
action of G.
~ be any X-labeled graph such that for each x ∈ X and each vertex
Proof. Let Θ
v, there is exactly one outgoing and one ingoing edge with label x. It is clear
~ is (strongly isomorphic to) a graph of an action of G = hX | Ri if and
that Θ
only if for every r ∈ R, and for every vertex v, the unique path with initial
vertex v and label r is closed.
Now, fix v a vertex in ~Γ, r a word on X t X −1 and 0 ≤ i < M . There is a
unique path p with initial vertex v and label r in ~Γ and a unique path q with

~ M . We have that τ (q) = τ (p), i+der(p) .
initial vertex (v, i) and label r in ~Γ⊗ C
Therefore, if r is a relator we have τ (q) = (τ (p), i) and p is closed if and only if
q is closed.
Using this lemma and Proposition 3.2.1 we have the following.

13

Proposition 3.3.2. Fix M ∈ N and let G = hX | Ri be a group presentation
such that expX (r) ≡ 0 (mod M ) for every relator r ∈ R. Let H be a subgroup
~
of G and let ~Γ := Sch(G,
H, X) be the corresponding Schreier graph. Then,
~ M is the Schreier graph of G with respect
every connected component of ~Γ ⊗ C
to X and to the subgroup HM := {h ∈ H | expX (h) ≡ 0 (mod M )}.
Proof. First, note that since expX (r) ≡ 0 (mod M ) for every relator r, the
exponent of g ∈ G is well defined modulo M . By Proposition 3.2.1 and Re~ M are strongly isomorphic. By
mark 3.2.1, all connected components of ~Γ ⊗ C
~ M is a graph of an action of G and therefore all its
the previous lemma, ~Γ ⊗ C
connected components are Schreier graphs of G.
Now, let v be a vertex in ~Γ corresponding to the subgroup H. The subgroup
~ M . By Lemma 3.1.1,
HM consists of labels of paths from (v, 0) to (v, 0) in ~Γ ⊗ C
for any signature σ, there is a bijection between the set of closed paths p with
initial vertex (v, 0) and signature σ and the set of couples (q, r) where q is a
closed path with initial vertex v, r a closed path with initial vertex 0, both of
~ M if and only
signature σ. But there is a path r from 0 to 0 with signature σ in C
if der(r) ≡ 0 (mod M ), and in this case there is a unique such path. Finally,
~ M is inherited from the
we conclude using the fact that the labeling of ~Γ ⊗ C
~
labeling of Γ.
~
Observe that if in Proposition 3.3.2, Γ = Cay(G,
X) then it corresponds
to a Schreier graph with H = {1} and thus HM = {1} and every connected
~ M is isomorphic to ~Γ itself.
component of ~Γ ⊗ C
Remark 3.3.2. Lemma 3.3.2 and Proposition 3.3.2 have a geometrical mean~M
ing. If for every relator r, expX (r) ≡ 0 (mod M ), then G naturally acts on C
~
~
:=
by i.g
i + expX (g). Therefore, the action of G on Γ ⊗ CM is the product of
the actions. In term of Schreier graphs, that exactly means that HM = H ∩LM ,
~M .
where LM is the subgroup of G which stabilizes the vertex i ∈ C

3.4

The case of lamplighter groups

By the lamplighter
Lgroup Lk , for k ≥ 2, we mean the restricted wreath product
Z/kZ
o
Z
'
Z Z/kZ oZ where Z acts on the normal subgroup Ak :=
L
Z/kZ
by
shifting
the coordinates. It is easy to see that it is given by the
Z
presentation
Lk := hb, c | ck , [c, bn cb−n ]; n ∈ Ni,
(†)

where [x, y] = x−1 y −1 xy is the commutator of x and y. Observe that this in
particular implies [bm cb−m , bn cb−n ] = 1 in Lk for all m and n in Z.
The subgroup Ak = ⊕Z Z/kZ, called the abelian base of the wreath product,
is generated by {bi cb−i }i∈Z , while Z is generated by b. The (right) action of b
on Ak is by shift, bi cb−i .b = bi−1 cb−i+1 .
Following [12], instead of the “classical” presentation (†) of Lk , in this paper
we will use the following presentation coming from the automaton presentation.
Consider the set Xk = {b, c̄1 , . . . , c̄k−1 }, where c̄i = bci . Note that c = b−1 c̄1 ,
so Xk does generate Lk . It will be convenient to write c̄0 for b = bc0 , so that
Xk = {c̄i }k−1
i=0 .
−1
Lk = hXk | (b−1 c̄1 )k , b(b−1 c̄1 )i c̄−1
c̄1 , bn−1 c̄1 b−n ]; n ∈ N, 2 ≤ i ≤ k − 1i.
i , [b
(‡)

14

It is possible to check that 1 does not belong to Xk and that x ∈ Xk implies
that x−1 ∈
/ Xk . In particular, the graph Cay(Lk , Xk ) is strongly isomorphic
~
to Cay(Lk , Xk ). It is interesting to note that with this particular choice of
generators, the graph Cay(Lk , Xk ) is weakly isomorphic to the Diestel-Leader
graph DL(k, k) (see [24]).
Remark 3.4.1. It is easy to see that, if G is any finite group and we consider
the restricted wreath product GoZ, where Z = hbi and choose the generating set
{bg}g∈G , then the corresponding Cayley graph will be also weakly isomorphic
to Cay(Lk , Xk ) and thus to the Diestel-Leader graph DL(k, k). For the rest of
the paper, we will focus on the lamplighter group Lk .
We immediately have
expX (b−1 c̄1 )k = expX b(b−1 c̄1 )i c̄−1
= expX ([b−1 c̄1 , bn−1 c̄1 b−n ]) = 0.
i
Hence, the presentation (‡) of Lk satisfies the hypothesis of Proposition 3.3.1
and we proved the following special case of Proposition 3.3.2.
Proposition 3.4.1. For all k ≥ 2 and M ∈ N, every connected component of
~
~
~
Cay(L
k , Xk ) ⊗ CM is strongly isomorphic to Cay(Lk , Xk ).

4

Spider-web graphs and lamplighter groups

A slightly different version of spider-web graphs, called spider-web networks,
was first introduced by Ikeno in [13]. The 2-parameter family {Sk,N,M } that we
will presently define is a natural extension of the well-known 1-parameter family
of the de Bruijn graphs {Bk,N }, k ≥ 2. In [1], Balram and Dhar observed, in
the special case k = 2, some link between spider-web graphs and the Cayley
graph of the lamplighter group L2 .
The aim of this section is to discuss the definition of spider-web graphs
Sk,N,M and to show that they converge to the Cayley graph of the lamplighter
group Lk . This is our Theorem 4.4.2 for the oriented case and Corollary 4.4.2
for the non-oriented case. In order to do that, we first prove Theorem 4.4.1
which shows that de Bruijn graphs are weakly isomorphic to Schreier graphs of
the lamplighter group.
From now on, we fix a k ≥ 2 and omit to write it when it is not necessary.
We will use the notations N = {1, 2, . . . }, N0 = N ∪ {0} and N = N ∪ {∞}.

4.1

De Bruijn Graphs

~k,N
Definition 4.1.1. For every N ∈ N0 , the N -dimensional de Bruijn graph B
N
on k symbols is the oriented labeled graph with vertex set {0, . . . , k − 1} and,
for every vertex x1 . . . xN , k outgoing edges labeled by R0 to Rk−1 . The edge
labeled by Ry has x2 . . . xN y as end vertex.
Sometimes de Bruijn graphs are defined as non-oriented graphs. In the
~N = B
~k,N for the oriented version and BN = Bk,N for
following, we will write B
~N .
the non-oriented one. Note that in our formalism, the graph BN is B
De Bruijn graphs are widely seen as representing overlaps between strings
of symbols and are also combinatorial models of the Bernoulli map x 7→ kx
(mod 1) and therefore are of interest in the theory of dynamical systems.
15

~N is the line graph (see
It is shown in [25] that each de Bruijn graph B
~
Definition 3.2) of the previous one, BN −1 . For the sake of completeness we
include here a proof of this fact which is crucial for our purposes.
~N +1 is (weakly)
Lemma 4.1.1 ([25]). For every N ∈ N0 , the de Bruijn graph B
~
isomorphic to the line graph of BN .
~1 is weakly isomorphic to the comProof. It is clear from the definition that B
~1 has k vertices and for
plete oriented graph on k vertices, with loops. That is, B
each pair (v, w) of vertices, there is exactly one edge from v to w. In particular,
~1 is
for every v there is a unique edge from v to itself. It is then obvious that B
~0 (the rose).
weakly isomorphic to the line graph of B
~N and each label Ry , there
Observe that, for any N , for each vertex v in B
is exactly one edge e with initial vertex v and label Ry . Therefore, there is a
~N and the set of
natural bijection between the vertex set of the line graph of B
~
couples {(v, Ry ) | v a vertex in BN , 0 ≤ y < k}. Let v = (x1 . . . xN ) be a vertex
~N . If N ≥ 1, there is an edge in the line graph from (v, Ry ) to (w, Rz ) if
in B
and only if w = (x2 . . . xN y).
We construct now an explicit weak isomorphism φ from the line graph of
~N to B
~N +1 . We define φ on the vertices by φ(v, Ry ) := (x1 . . . xN y) if v =
B
(x1 . . . xN ). This is obviously a bijection.
If N ≥ 1, there

 is a unique edge in
the line graph from (x1 . . . xN ), Ry to (x2 . . . xN y), Rz (and all edges are of
~N +1 with
this form). Let the image of this edge by φ be the unique edge in B
initial vertex (x1 . . . xN y) and label Rz — see Figure 2. It is straightforward
to see that φ is injective on the set of edges. Since the two graphs have the
same finite number of edges (k · k N +1 ), φ is also bijective on the set of edges.
Moreover, by definition, φ ι(e) = ι φ(e) for any edge e in the line graph.
Hence, to show that
φ is a weak isomorphism it only remains to check that


φ τ (e) = τ φ(e) . If e is an edge from (x1 . . . xN ), Ry to (x2 . . . xN y), Rz ,
we have

φ τ (e) = (x2 x3 . . . xN yz).
On the other hand, φ(e) has initial vertex (x1 . . . xN y) and label Rz . Therefore,


τ φ(e) = (x2 x3 . . . xN yz) = φ τ (e) .
(x3 . . . xN yz)
(x2 . . . xN yz)

Rz
φ

e

(x2 . . . xN y)

7−→

Ry

Rz
(x1 . . . xN y)

(x1 . . . xN )
~N and its image by φ.
Figure 2: The edge e in the line graph of B

16

4.2

Spider-web graphs

Definition 4.2.1. Let k ≥ 2. For all M ∈ N and N ∈ N0 , the spider-web
graph is the labeled oriented graph S~N,M = S~k,N,M with vertex set {0, . . . , k −
1}N ×{1, 2, . . . , M } and for every vertex v = (x1 . . . xN , i) with k outgoing edges
labeled by R0 to Rk−1 . The edge labeled by Ry has (x2 . . . xN y, i + 1) as end
vertex, where i + 1 is taken modulo M . See figure 3 for an example.
i

0

1

2

3

4

x1 x2 x3
000
001
010
011
100
101
110
111
Figure 3: The graph S~2,3,4 , where vertices in the slice i = 0 are identified with
vertices in the slice i = M = 4. Solid edges correspond to edges with label R1
and dotted edges to edges with label R0 .
As with de Bruijn graphs, we write S~N,M for the oriented version and
SN,M for the non-oriented one. The vertices of SN,M are partitioned into slices
1, . . . , M and edges connect vertices in slice i to vertices in slice i + 1 (mod M ).
Note that in our definition (unlike papers that talk about spider-web networks),
the vertices of the slice M are connected to the vertices of the slice 1. Note
also that it is possible to similarly define S~k,N,∞ for all N (with vertex set
{0, . . . , k − 1}N × Z).
Observe that the graph S~k,0,M is a “thick” oriented circle (or line if M = ∞):
the vertex set is M and for every vertex i there are k edges from i to i + 1. The
~ M . Therefore, S~k,0,1 is the rose with
graph S~1,0,M is the usual oriented circle C
one vertex and k oriented edges.
Lemma 4.2.1. For all M ∈ N and N ∈ N0 there is a strong isomorphism
~M .
between S~N,M and S~N,1 ⊗ C
Remark 4.2.1. Observe that this lemma is not true if we consider the nonoriented spider-web graphs. This is the main reason why we are brought to
17

work with oriented graphs in this article, even though the final result that we
aim at and that we get are about non-oriented graphs (Corollary 4.4.2).
Lemma 4.2.1 together with Theorem 3.1.1 ensures that in order to identify
the limit of spider-web graphs when M, N → ∞ it is enough to study the limit
of spider-web graphs with M = 1. It turns out that the spider-web graphs with
M = 1 are exactly de Bruijn graphs.
Indeed the identification given by (x1 . . . xN , 1) 7→ (x1 . . . xN ) induces a
~N . The isomorphism between nonstrong isomorphism between S~N,1 and B
oriented versions follows. Hence we have the following.
Proposition 4.2.1. For all N ∈ N0 , the oriented graph S~N,1 is strongly iso~N and the non-oriented graph SN,1 is strongly isomorphic to BN .
morphic to B
Lemma 4.2.1 directly implies the following.
Corollary 4.2.1. For all M ∈ N and N ∈ N0 , S~N,M is strongly isomorphic to
~N ⊗ C
~M .
B
01
0

1

00

11

10
001

011

000

111
010

101

100

110

Figure 4: Oriented de Bruijn graphs for k = 2 and N ∈ {1, 2, 3}. Solid edges
correspond to edges with label R1 and dotted edges to edges with label R0 .
Lemma 4.2.2. For all M ∈ N and N ∈ N0 , the graph SN,M is connected.
~N ⊗ C
~ M . On the other side,
Proof. By the previous corollary, S~N,M ' B
~
der(BN ) = 1 since there is a loop (labeled by R0 ) at the vertex (0 . . . 0).
Therefore, by Proposition 3.2.2, the number of connected components of S~N,M
is 1.

4.3

The group Lk and its action on the k-regular rooted
tree

We will use the language of actions on rooted trees, see for instance [11] and [17].
18

Fix k ≥ 2. The strings over the alphabet A = {0, 1, . . . , k − 1} are in one-toone correspondence with the vertices of the k-regular rooted tree Tk where the
root vertex corresponds to the empty string. Under this correspondence, the
nth level of Tk is the set of strings over A of length n. The boundary ∂Tk of Tk
is the set of right infinite strings over A. We write T k := Tk ∪ ∂Tk .
We also have a one-to-one correspondence between Tk and the ring of polynomials Z/kZ[t] given by
(x0 . . . xn ) 7→ x0 + x1 t · · · + xn tn
and a one-to-one correspondence between ∂Tk and the ring of formal series
Z/kZ[[t]] given by
X
(x0 x1 x2 . . . ) 7→
xi t i .
(?)
i≥0

Let G ≤ Aut(Tk ) be a group acting on Tk by automorphisms. The action is
said to be spherically transitive if it is transitive on each level.
Extending a result from Grigorchuk and Żuk [12] for k = 2, Silva and Steinberg showed in [23] that the lamplighter group Lk introduced in Subsection 3.4
above acts on T k . They showed that this action is faithful and spherically transitive and described some other interesting properties of this action. Here, we
will look at the action given by

(x1 x2 x3 . . . ).c̄r = (x1 + r)(x2 + x1 )(x3 + x2 ) . . .

where additions are taken modulo k. This action is slightly different from the
one in [23], but remains faithful and spherically transitive.
Since the action of L on T is spherically transitive, for any generating set
Y , for all N , the graph of the action on the N th level are connected. Thus,
~
they can be viewed as Schreier graphs Sch(L,
HN , Y ), where HN = StabL (vN ),
th
with vN any vertex of the N level of T . On the other hand, it is obvious
that the graph of the action on ∂T is not connected. Its connected components
correspond to the orbits of the (countable) group L on the (uncountable) set
∂T . They can be viewed as Schreier graphs of the subgroups StabL (ξ), ξ ∈ ∂T .
If v, w are two vertices of T , with w lying on an infinite ray emanating from v,
then StabL (w) is a subgroup of StabL (v). This implies that for every N , the
~
~
graph Sch(L,
HN +1 , Y ) covers Sch(L,
HN , Y ), and we deduce the following.

Proposition 4.3.1 ([10],[15]). For any generating set Y and any ξ = (x1 x2 . . . )

~
HN , Y ), (x1 . . . xn ) converges
ray in ∂T , the sequence of rooted graphs Sch(L,
(as labeled graphs) to

~
Sch(L,
StabL (ξ), Y ), ξ .
We also have

Proposition 4.3.2 ([10],[15]). For all but countably many ξ ∈ ∂T , the oriented
~
~
graph Sch(L,
StabL (ξ), Y ) is strongly isomorphic to Cay(L,
Y ).

~
Proof. The oriented labeled graph Sch(L,
StabL (ξ), Y ), ξ is strongly isomor~
phic to Cay(L, Y ) if and only if StabL (ξ) = {1}. We will show that StabL (ξ) 6=

19

{1} for only countably many ξ. In order to prove that, we look at the equivalent
action of L on Z/kZ[[t]]. Applying formula (?) we set for any F ∈ Z/kZ[[t]]
F.c = F + 1
F.b = (1 + t)F.
Hence for any i we have
F.b−i cbi = F + (1 + t)i .
Let 1 6= g be an element in L. Then g admits a unique decomposition as g = bi h
for some i ∈ Z and h ∈ A = h{bj cb−j }j∈Z i. Therefore, there exists P a finite
sum of (1 + t)j ’s, j ∈ Z, such that for any F ∈ Z/kZ[[t]],
F.g = (1 + t)i F + P
F.g

−1

and

−i

−i

= (1 + t) F − (1 + t) P.

Since the action is faithful (and g 6= 1), it is not possible that i = 0 and P = 0
together. Now, suppose F has non-trivial stabilizer. Then there exists 1 6= g ∈ L
such that F = F.g = F.g −1 and therefore F is a solution to the equations

(1 + t)i − 1 x = −P

(1 + t)−i − 1 x = (1 + t)−i P.
We have i 6= 0, otherwise we would have P = 0, which is absurd. Hence, F is a
solution of

(1 + t)i − 1 x = Q,
(∗)

with i > 0 and Q belonging to L := Z/kZ[(1 + t), (1 + t)−1 ], the subring of
Z/kZ[[t]] consisting of Laurent polynomials in 1 + t. Note that
(1 + t)i − 1 is

i
not invertible and thus we cannot write x = Q/ (1 + t) − 1 .
Suppose for a moment that k is prime. This is equivalent to Z/kZ[[t]] being
an integral domain. In this case, given a 6= 0 and b in Z/kZ[[t]], the equation
ax = b has at most one solution. Now, if F has a non-trivial stabilizer, we had
just proved that it satisfies equation (∗). Since L is countable, there are only
countably many equations of this form and, by unicity of solution, countably
many solutions of such equation and hence countably many F with non-trivial
stabilizer.
If k is not prime, we do not have the unicity of solution of equations in
Z/kZ[[t]]. For example, for k = 6 the equation 2t · x = 0 admits uncountably
many different solutions (all series x where all coefficients belongs to {0, 3}).
But, in our special case, we claim that (∗) has only finitely many solutions.
Using that, we have again that the number of series F with non-trivial stabilizer
is countable.
We now prove the claim. If equation (∗) has no solution, then the claim is
true. If there is as at least one solution, the solutions of (∗) are in one-to-one
correspondence with the solutions of

(1 + t)i − 1 x = 0.
But such an equation has only finitely many solutions by the following lemma.

20

Lemma 4.3.1. Let R be a finite ring and P =
Then, in R[[t]], the equation P x = 0 has

Pd

j=0

pj tj ∈ R[t] a polynomial.

1. only one solution (x = 0) if the first non-zero coefficient of P does not
divide 0;
d

2. at most |R| solutions if pd is invertible.
Proof. The first statement is trivially true.
The
P proof of the second statement is by contradiction. Observe that if
x = n≥0 xn tn is a solution, we have for all n
xn = −p−1
d

d
X

pd−k xn+k .

k=1
d

Now, suppose that the equation P x = 0 has more than |R| solutions. Choose
d
|R| +1 different solutions yi . There exists an integer l such that all the ȳi differ,
Pl
d
where x̄ = n=0 xn tn is the series x up to degree l. We hence have |R| + 1
distinct polynomials of degree at most l, all satisfying the identities above. But
d
this is not possible. Indeed, we have at most |R| different choices for the
l
l−d+1
coefficients of t to t
and all other coefficients are uniquely determined by
these ones.
Until here, all the results of this subsection were true for any generating set Y
of Lk . In the following, we will work with our usual generating set Xk = {c̄i }k−1
i=0 .
Notation 4.3.1. Denote by ~Γk the oriented labeled graph of the action of Lk
on T k , with respect to the generating set Xk . If we restrict this action to the
N th level of Tk , the corresponding oriented labeled graph of the action will be
denoted by ~Γk,N . The graph corresponding to the restriction of the action to
∂Tk will be denoted by ~Γk,∞ .
As with spider-web graphs and de Bruijn graphs, from now on we omit k
from our notation and write simply L, T , X, ~Γ, ~ΓN and ~Γ∞ .
The following proposition will, together with Lemma 4.1.1, help to establish
a connection between the lamplighter group and the de Bruijn graphs.
Proposition 4.3.3. For every N ∈ N0 , the graph ~ΓN +1 is (weakly) isomorphic
to the line graph of ~ΓN .
Proof. First, we have that ~Γ0 is the rose with k loops and ~Γ1 is the complete
oriented graph (with loops) on k vertices. Therefore ~Γ1 is weakly isomorphic to
the line graph of ~Γ0 .
We have that the set of vertices in the line graph of ~ΓN is in bijection with
the set of couples
{(v, c̄i ) | v a vertex in ~ΓN , 0 ≤ i < k}.
Let v = (x1 . . . xN ) be a vertex in ~ΓN . If N ≥ 1, there is an edge in the line graph

from (v, c̄i ) to (w, c̄j ) if and only if w = v.c̄i = (x1 +i)(x2 +x1 ) . . . (xN +xN −1 ) .
We construct now an explicit weak isomorphism φ from the line graph
 of
~ΓN to ~ΓN +1 , see Figure 6. We define φ on the vertices by φ (x1 . . . xN , c̄i ) :=
21

10
0

1

00

01

11
100

110

000

001
010

011

111

101

Figure 5: The graphs ~Γ2,N for N ∈ {1, 2, 3}. Solid edges correspond to edges
with label c̄1 and dotted edges to edges with label c̄0 .
(ix1 . . . xN ). It is easy to see that φ is injective (and hence bijective) on vertices.

If N ≥ 1, there is a unique edge in the line graph from (x1 . . . xN ), c̄i to
(x1 + i)(x2 + x1 ) . . . (xN + xN −1 ), c̄j (and all edges are of this form). Let
the image of this edge by φ be the unique edge in ~ΓN +1 with initial vertex
(ix1 . . . xN ) and label c̄j−i — see Figure 6. It is straightforward to see that φ
is injective
(andthus bijective) on the set of edges. Moreover, by definition,

φ ι(e) = ι φ(e) for any edge e in the line graph. Hence,
 to show that φ is a
weak isomorphism it only remains to check that φ τ (e) = τ φ(e) . If e is an
edge from (x1 . . . xN ), c̄i to (x1 + i)(x2 + x1 ) . . . (xN + xN −1 ), c̄j , we have


φ τ (e) = j(x1 + i)(x2 + x1 ) . . . (xN + xN −1 ) .
On the other hand, φ(e) has initial vertex (ix1 . . . xN ) and label c̄j−i . Therefore,



τ φ(e) = (i + j − i)(x1 + i)(x2 + x1 ) . . . (xN + xN −1 ) = φ τ (e) .

4.4

Convergence of the spider-web graphs to the Cayley
graph of the lamplighter group

In this subsection, we use results of the last two subsections to finally establish
a link between the spider-web graphs S~k,N,M and the graph ~Γk of the action
of the lamplighter group Lk on the k-regular tree T k and to prove our main
results.
~k,N is
Theorem 4.4.1. Let k ≥ 2. For all N ∈ N0 , the de Bruijn graph B
th
weakly isomorphic to ~Γk,N , the graph of the action of Lk on the N level of Tk ,
with respect to the generating set Xk = {c̄r }k−1
r=0 (see (‡) on page 14).
22

w
j(x1 + i)(x2 + x1 ) . . . (xN + xN −1 )

c̄j

(x1 + i)(x2 + x1 ) . . . (xN + xN −1 )

φ

e

7−→



c̄j−i

c̄i
(ix1 . . . xN )
(x1 . . . xN )
Figure 6: The edge e in the line graph of ~ΓN and its image by φ.
Proof. The proof goes by induction on N . For N = 0, both graphs are weakly
isomorphic to the rose with k loops. For N ≥ 1 we have by Lemma 4.1.1
~k,N is weakly isomorphic to the line graph of B
~k,N −1 . Since B
~k,N −1 is
that B
~
(by induction) weakly isomorphic to Γk,N −1 and that the line graph does not
~k,N and the line
depend on the labeling we have a weak isomorphism between B
graph of (~Γk )N −1 . By Proposition 4.3.3, this graph is itself weakly isomorphic
to (~Γk )N .
~k,N
Remark 4.4.1. These graphs are not strongly isomorphic. Indeed, in B
for every vertex v, all edges ending at v have the same label, but in a Schreier
graph two edges having the same end-vertex have distinct labels. (See Figures 4
and 5.)
Theorem 4.4.1 and the fact that ~Γk,N covers ~Γk,N −1 (see the discussion before
Proposition 4.3.1), imply the following property of de Bruijn graphs that, as far
we know, was not observed before.
~N (weakly) covers B
~N −1 .
Corollary 4.4.1. For all N ∈ N the graph B
We are now able to prove our main theorem.
Theorem 4.4.2. Let k ≥ 2. Recall that Lk denotes the lamplighter group
(Z/kZ) o Z and Xk = {c̄r }k−1
r=0 is the generating system given by (‡), see page 14.
~k,N converge to Cay(L
~
1. The unlabeled oriented de Bruijn graphs B
k , Xk ) in
the sense of Benjamini-Schramm convergence (see Definition 2.4).
2. The following diagram commutes, where the arrows stand for BenjaminiSchramm convergence of unlabeled graphs.
N
S~k,N,M

M

∞

N,

M
∞

∞

S~k,N,∞

~
Cay(L
k , Xk )

∞

N

23

~
Cay(L
k , Xk )

Proof. By Proposition 4.3.2, for all but countably many ξ = (x1 x2 . . . ) in
∂Tk , the oriented graph (~Γk,∞ , ξ)0 is strongly isomorphic to the oriented Cay~
ley graph Cay(L
k , Xk ). On the other hand, by Proposition 4.3.1, the graphs

~Γk,N , (x1 . . . xN ) strongly converge to (~Γk,∞ , ξ)0 . Theorem 4.4.1 gives us
~k,N and ~Γk,N . Therefore, B
~k,N converge to
a weak isomorphism between B
~
Cay(L
k , Xk ). This ends the proof of the first part of the theorem.
In order to prove the second part of the theorem, we should consider an
auxiliary diagram, see Figure 7. First note that we already know that when
~k,N , vN ) weakly converge to the Cayley graph
N → ∞ de Bruijn graphs (B
~
(Cay(Lk , Xk ), 1Lk ) for nearly all choices of the vN and that it is obvious that
~ 0) when M → ∞. Hence, by Theorem 3.1.1, the
~ M , 0) weakly converge to (Z,
(C
diagram in Figure 7 is commutative. Finally, since this statement is true for
nearly all choices of roots, we have the convergence in the sense of BenjaminiSchramm when we choose the roots uniformly. By Proposition 3.4.1, for every
~k,N ⊗ C
~ M , (vk,N , 0)
B
M

∞

~ (vk,N , 0)
~k,N ⊗ Z,
B

0

0

∞

N

~
~
Cay(L
k , Xk ) ⊗ CM , (1Lk , 0)
M

N ,M
∞

∞

~
~
Cay(L
k , Xk ) ⊗ Z, (1Lk , 0)

∞

N

0

0

Figure 7: Limit of de Bruijn graphs
~
~
M ∈ N, any connected component of Cay(L
k , Xk ) ⊗ CM is strongly isomorphic
~
to Cay(Lk , Xk ); in particular, this does not depend on M . On the other hand,
~k,N ⊗ C
~ M is strongly isomorphic to S~k,N,M by Corollary 4.2.1,
for all M ∈ N, B
and therefore is connected.
Using Proposition 2.1, we obtain the same result for non-oriented versions
of de Bruijn and spider-web graphs as an immediate corollary.
Corollary 4.4.2.
1. The unlabeled de Bruijn graphs Bk,N converge to Cay(Lk , Xk ) in the sense
of Benjamini-Schramm convergence (see Definition 2.4).
2. The following diagram commutes, where the arrows stand for BenjaminiSchramm convergence of unlabeled graphs.
Sk,N,M

∞

N

N,

M

∞

∞

Sk,N,∞

Cay(Lk , Xk )

M

∞

N

Cay(Lk , Xk )

Remark 4.4.2. Remark 3.4.1 implies that in Theorem 4.4.2 and its Corollary 4.4.2, Lk can be replaced by any wreath product G o Z, where G is a finite
group of cardinality k. However, Theorem 4.4.1 does not hold necessarily if G
is not abelian.
24

5

Computation of spectra

In this section we compute the characteristic polynomial and the spectrum of
the adjacency matrix of SN,M for all M, N ∈ N. The spectra of the graphs {ΓN }
of the action of L2 on the levels of the binary rooted tree were first computed by
Grigorchuk and Żuk in [12] using the fact that they form a tower of coverings,
see the discussion just before Proposition 4.3.1. (Note that the multiplicity in
their formula is not completely correct – compare with our Theorem 5.1 below.)
These computations were extended to any wreath product G o Z, with G 6= {1}
finite, by Kambites, Silva and Steinberg in [15], using automata theory. Dicks
and Schick [6] computed the spectral measures for random walks on G o Z using
entirely different methods (see also [2]).
~N in [5]
On the other hand, Delorme and Tillich computed the spectra of B
using simple matrix transformations. It is well known that for any pair of square
matrices A and B with respective eigenvalues (λi )ni=1 and (µj )m
j=1 , the spectrum
of A ⊗ B is {λi µj | 1 ≤ i ≤ n, 1 ≤ j ≤ m}. However, this formula cannot be
~N ⊗ C
~ M and
applied in our case since we want to compute the spectrum of B
there is no formula relating eigenvalues of a matrix A (the adjacency matrix of
an oriented graph) and of its symmetrized matrix A + A∗ (the adjacency matrix
of the underlying graph). Instead we generalize Delorme and Tillich method
directly to all SN,M .
For A a matrix, we denote its characteristic polynomial by χ(A). For a
graph (oriented or not, etc.) Γ, the characteristic polynomial χ(Γ) of Γ is
the characteristic polynomial of its adjacency matrix. The following lemma
summarizes discussions 2.(1), 2.(2) and 2.(3) from [5].
Lemma 5.1. Let ~Γ be an oriented graph, ~Γ the underlying non-oriented graph
~ and A their respective adjacency matrices. Suppose that there exist comand A
~ = U ∗ DU . Then χ(~Γ) =
plex matrices D and U with U unitary such that A
∗
∗
~
χ(D). Moreover, A = U (D + D )U and χ(Γ) = χ(D + D∗ ).
~ + (A)
~ ∗ = U ∗ DU + U ∗ D∗ U = U ∗ (D + D∗ )U . On
Proof. We have A = A
the other hand, A and D are equivalent matrices and therefore have the same
characteristic polynomial.
Observe that for a given complex matrix D we can construct an oriented
~ with adjacency matrix D, where a weighted graph is a graph
weighted graph Θ
Γ = (V, E) (oriented or not, labeled or not, etc.) with a map w : E → C which
assign to each edge a complex number (a weight) such that w(ē) is the complex
~
conjugate of w(e). In this case, D + D∗ is the adjacency matrix of Θ.
In their article, Delorme and Tillich use this to compute the spectrum of de
Bruijn graphs BN and prove the following.
~ k,N be the weighted
Proposition 5.1 (Dellorme-Tillich). For all N ∈ N0 , let Θ
oriented graph which is the disjoint union of
1. one oriented loop,
2. for all 0 ≤ i ≤ N − 2, (k − 1)2 k N −i−2 disjoint oriented paths of length i,
3. k − 1 disjoint oriented paths of length N − 1;
25

where all edges have weight k and an oriented path of length i is the oriented
graph with vertex set V := {0, . . . , i} and for every vertex j ∈ V a unique edge
~ N be the adjacency matrix of this graph
from j to j + 1 (see Figure 8). Let D
~
~
and BN be the adjacency matrix of BN . Then there exists U = UN unitary with
~ N = U ∗D
~ NU.
B
k

k

k

k

k

Figure 8: An oriented weighted path of length 5, where all edges have weight k.

2

2

2
2

~ 2,3 .
Figure 9: The oriented weighted graph Θ
~ 2,3 .
See Figure 9 for the example of Θ
The only thing remaining to do in order to compute the characteristic poly~N,M of S~N,M using B
~N.
nomial of S~N,M is to express the adjacency matrix S
But it is well known that, for non-oriented graphs, the adjacency matrix of a
tensor product is the tensor (or Kronecker) product of adjacency matrices. This
is also trivially true for oriented graphs. Therefore, we have
~N,M = B
~N ⊗ A
~M ,
S
~ M , the adjacency matrix of the oriented cycle C
~ M , has a 1 in position
where A
~
~N ⊗A
~ M , a simple
(i, j) if and only if j ≡ i + 1 (mod M ). Denoting DN,M := D
computation gives us
~N,M = B
~N ⊗ A
~M
S
~ N U ) ⊗ (Id∗ A
~ M Id)
= (U ∗ D

~N ⊗A
~ M )(U ⊗ Id)
= (U ∗ ⊗ Id∗ )(D
~ N,M )(U ⊗ Id),
= (U ⊗ Id)∗ (D

where Id is the identity matrix of size M . Since U and the identity matrix are
both unitary, their tensor product U ⊗ Id is also unitary. Thus, by Lemma 5.1,
~ N,M + D
~ ∗ ).
the characteristic polynomial of SN,M is equal to χ(D
N,M
~ N,M is the adjacency matrix of the weighted graph
On the other hand, D
~ k,N,M := Θ
~ k,N ⊗ C
~ M . Computing this tensor product we have that the
Θ
~ k,N,M is the disjoint union of
weighted graph Θ
1. one oriented cycle of length M ,
2. for all 0 ≤ i ≤ N − 2, M (k − 1)2 k N −i−2 disjoint oriented paths of length i,
3. M (k − 1) disjoint oriented paths of length N − 1;
26

~ N,M +
where all edges have weight k — see Figure 10 for an example. Hence, D
∗
~
~
DN,M is the adjacency matrix of Θk,N,M . Therefore
∗
~ N,M + D
~ N,M
χ(SN,M ) = χ(D
)

= Q(x) · PN (x)M (k−1)

N
−1
Y

2 N −i−1

Pi (x)M (k−1)

k

,

i=1

where Q(x) = Qk,M (x) is the characteristic polynomial of the non-oriented cycle
of length M with all edges of weight k and Pi (x) = Pi,k (x) is the characteristic
polynomial of the non-oriented path of length i − 1 with all edges of weight k.
We now want to have an explicit form for the Pi ’s and Q. In [5], Delorme and
2 2

2

2

2

2

2

2

~ 2,3,2 .
Figure 10: The oriented weighted graph Θ
Tillich showed that Pi (x) = k i Vi (x/k) with Vi the Chebyshev polynomial of the
second kind of degree i. The set of roots of Pi (x) is exactly
 tπ 
{2k cos
| 1 ≤ t ≤ i}
i+1

and all roots are simple. On the other hand, Q(x) is the characteristic polynomial of the adjacency matrix of a non-oriented cycle of length M with edges of
weight k. If M 6= 1, all the non-zero entries of this matrix have value k and are
in position (i, j) with |i−j| = 1. If M = 1, the cycle is a loop of length k and the
adjacency matrix consists of a unique entry: 2k. In both cases, the adjacency
matrix is a circulant matrix of size M and it has characteristic polynomial
Q(x) =

M
 2πl 
Y
(x − 2k cos
).
M
l=1

That is, the root 2k has multiplicity 1, the root −2k has multiplicity 1 if M is
even and multiplicity 0 otherwise and for all 1 ≤ l < M/2 the root 2k cos( 2πl
M )
has multiplicity 2. Therefore we have just proved the following.
For every k ≥ 2, N ∈ N0 , and M ∈ N, the spectrum of SN,M consist of 2k
with multiplicity 1, of
p 
{2k cos π | 1 ≤ p < q ≤ N + 1; p and q relatively prime},
q
with multiplicity not specified yet and, if M is even, also of −2k with multiplicity 1.
 
The computation of the multiplicity of 2k cos pq π for a given p and q is

done in four steps. Step one: compute its multiplicity in eigenvalues (interpreted as roots) of Q(x); it is either 0 or 2. Step two: compute its multiplicity
27

in PN (x)M (k−1) ; it is either 0 or M (k−1). Step three: for all 1 ≤ i ≤ N −1, com2 N −i−1
pute its multiplicity in Pi (x)M (k−1) k
; it is either 0 or M (k − 1)2 k N −i−1 .
Step four: add the results of the three previous steps.
In step one, the multiplicity is non-zero if and only if there exists 1 ≤ l < M
2
such that cos(2πl/M ) = cos(pπ/q). But this is possible if and only if l =
M p/2q ≥ 1. Since l is an integer and p and q are relatively prime, the multiplicity is 2 if and only if 2q divides M p.
In step two, the multiplicity is non-zero if and only if t = p(N + 1)/q, if and
only if q divides N + 1.
In step three, the multiplicity is non-zero if and only if t = p(i + 1)/q, if and
only if q divides i + 1.
Summing up all these quantities
we conclude that for 1 ≤ p < q ≤ N + 1,

the multiplicity of 2k cos pq π in the spectrum of SN,M is
2

M (k − 1) ·
with

bN
q c

X

k

N −jq

j=1

!

(
1
r1 = r1 (q, N ) =
0

and
r2 = r2 (p, q, M ) =

(

+ M (k − 1)r1 + 2r2 ,

if q divides N + 1
otherwise
1
0

2q divides M p
otherwise.

Observe that in the above sum, the first summand is equal to
!
bN
bN
q c
q c
X
X
2
N −jq
2 N
M (k − 1) ·
k
= M (k − 1) k ·
k −jq
j=1

j=1

2 N

= M (k − 1) k

!
N
1 − k −q(b q c+1)
−1 .
1 − k −q

In the case where q = N + 1, the multiplicity of 2k cos( Np+1 π) is M (k − 1) + 2r2 .
If M = 1, q cannot divide M (q is at least 2), thus in this case r2 is always equal
to 0.
If Γ is a finite graph with m vertices and with eigenvalues of the adjacency
matrix λ1 ≥ · · · ≥ λm , we write
m

µΓ =

1 X
δλ
m i=1 i

for the spectral measure on Γ, where δx denotes the Dirac mass on x. Then we
have the following.
Theorem 5.1. The spectral measure µSN,M of SN,M is, if M is odd,
1
δ2k
M kN
X
+
δ2k cos( pq π)

(k − 1)

2



!

N
1 − k −q(b q c+1)
k−1
2
− 1 + N r1 +
r2
1 − k −q
k
M kN
28

where the sum is over all 1 ≤ p < q ≤ N + 1 with (p, q) = 1.
If M is even, there is one more summand: M1kN δ−2k .
Remark 5.1. It directly follows from the formula in the above theorem that
for k and N fixed, SN,M and SN,M 0 have the same spectrum, except maybe for
the value −2k, and that the total variation distance between µSN,M and µSN,M 0
is bounded by k2N , independently from M and M 0 .
Since spider-web graphs converge, in the sense of Benjamini-Schramm, to
the Cayley graph Cay(Lk , Xk ) we retrieve the Kesten spectral measure of the
graph Cay(Lk , Xk ). This measure was first computed by Grigorchuk and Żuk
in [12] for k = 2 and then by Dicks and Schick in [6] and by Kambites, Silva and
Steinberg in [15] for the more general case G o Z, with G 6= {1} a finite group.

X 1  X
2
δ2k cos( pq π) .
(#)
µCay(Lk ,Xk ) = (k − 1)
kq − 1
q≥2

6

1≤p<q
(p,q)=1

General results on spider-web graphs

In 4.4.1 we proved that S~N,1 are weakly isomorphic to Schreier graphs of the
lamplighter group L. Other spider-web graphs are so far described as S~N,M '
~ M . In this section we will show that S~N,M is also a Schreier graph
S~N,1 ⊗ C
of L for each M, N . Then we characterize which of the S~N,M are transitive.
Finally, we generalize to spider-web graphs some statements that are known for
de Bruijn graphs: existence of Eulerian and Hamiltonian paths, the property of
being a line graph and some facts about covering.
As before we fix a k ≥ 2 and omit to write it when it is not necessary. We will
write N0 for {0, 1, 2, . . . } and N for {1, 2, . . . , ∞}. We also take X = {c̄i }k−1
i=0
(see (‡) on page 14) as generating set for the lamplighter group L.

6.1

Spider-web graphs as Schreier graphs of lamplighter
groups

~N is weakly isomorphic
In Theorem 4.4.1 we proved that the de Bruijn graph B
to a Schreier graph of L by using line graphs. Let us denote WN,1 := StabL (0N ).
Then we have the following.
Theorem 6.1.1. For all M ∈ N and N ∈ N0 , the spider-web graph S~N,M is
weakly isomorphic to
~
Sch(L,
WN,M , X)
where WN,M = {g ∈ WN,1 | expX (g) ≡ 0 (mod M )}.

~N is weakly isomorphic to ~ΓN , the spider-web graph S~N,M '
Proof. Since B
~N ⊗ C
~ M is weakly isomorphic to ~ΓN ⊗ C
~ M which is a Schreier graph of L by
B
Proposition 3.3.2 and the description of WN,M follows.

Remark 6.1.1. Geometrically, we are here in the situationQdescribed in Re~ M is given by j.( j (bit cb−it )rt ·
mark 3.3.2, where the action of L on C
t=1
t
brb ) = j + rb (mod M ). Indeed, bit cb−it = c̄i0t −1 c̄1 c̄−i
and therefore we have
0
Qj
expX ( t=1 (bit cb−it )rt · brb ) = rb .
29

Given a graph, a group and a generating set, there could be a priori many
different ways to represent the graph as a Schreier graph of the group. It
is
check that every g 6= 1 in L, can be written in a unique way as
Qjeasy itto −i
t rt
(b
cb
) · brb , where j, rb , rt , it ∈ Z with j ≥ 0 and 0 < rt < k for all
t=1
1 ≤ t ≤ j. This allows us to define a subgroup HN,M of L as the following set:
HN,M :=







g=

j
Y

(bit cb−it )rt · brb

t=1


rb ≡ 0 (mod M )


X
∈ L ∀i, 1 ≤ i ≤ N,
rt ≡ 0 (mod k) ,

N
it ≡i

where the second sum is over all it ≡ i (mod N ).

Theorem 6.1.2. For all M ∈ N and N ∈ N0 , the spider-web graph SN,M is
weakly isomorphic to Sch(L, HN,M , X −1 ).
Proof. Define the following permutations on the vertex set V of S~N,M :
(x1 . . . xN , j).b := (xN x1 . . . xN −1 , j − 1)

(x1 . . . xN , j).c := (x1 − 1)x2 . . . xN , j

where x1 − 1 is taken modulo k and j − 1 modulo M . The group G generated
by b and c acts on V .
An easy check shows that b and c satisfies the relations in the presentation
(†) (page 14) of L. Therefore G is a quotient of L, which implies that L acts too
on V . Moreover, for the generating set X −1 = {c̄−1
i } there are exactly k edges
in the graph of the action with initial vertex (x1 . . . xN , j): the one labeled by
(c̄r )−1 = c−r b−1 having (x2 . . . xN (x1 + r), j + 1) as end vertex. On other hand,
in S~N,M there are also exactly k edges with initial vertex (x1 . . . xN , j): the one
labeled by Ry having (x2 . . . xN y, j + 1) as end vertex. Since vertex sets and
adjacency relations (if we forget about labeling) are the same, S~N,M is weakly
isomorphic to the graph of the action of L on V with respect to the generating
set X −1 . Moreover, this graph being connected, it is also weakly isomorphic
~
to the Schreier graph Sch(L,
HN,M , X −1 ), with HN,M = StabL (0 . . . 0, 0). A
straightforward calculation gives us HN,M .
Finally, since we have an isomorphism between oriented graphs, there is an
isomorphism between the underlying non-oriented graphs.
In [10] Grigorchuk and Kravchenko classified subgroups of L and gave a
criterion for normality.
We now recall these two results and identify HN,M and WN,M according to
this classification. We then are able to see which of the subgroups are normal
(in which case the corresponding Schreier graphs are in fact Cayley graphs).
Recall that A = ⊕Z Z/kZ is the abelian part of L and that b acts on A by
shift.
Lemma 6.1.1 ([10], Lemma 3.1). Let H be a subgroup of L. Then it defines
the triple (s, H 0 , v) where s ∈ N is such that sZ is the image of the projection of
H on Z, H 0 = H ∩ A, satisfying H 0 .bs = H 0 , and v ∈ A is such that vbs ∈ H.
The v is uniquely defined up to addition of elements from H 0 . For s = 0 one
can choose v = 1L .
30

Conversely any triple (s, H 0 , v) with such properties gives rise to a subgroup
of Lk . Two triples (s, H 0 , v) and (s0 , G0 , v 0 ) define the same subgroup if and
only if s = s0 , H 0 = G0 and vH 0 = v 0 G0 . Moreover, H ⊆ G if and only if s0 |s,
Qs/s0
0
H 0 ⊆ G0 and v ≡ i=0 (v 0 .bis ) (mod G0 ).
Lemma 6.1.2 ([10], Lemma 3.2). Let H be a subgroup of L. Then H is normal if and only if the corresponding triple (s, H 0 , v), satisfies the additional
properties that H 0 .b = H 0 , v(v.b)−1 ∈ H 0 and g(g.bs )−1 ∈ H 0 for all g ∈ A.

Note that in [10] only the case of k prime is treated. However both lemmas
remain true for all k.
Proposition 6.1.1.
1. For all M ∈ N and N ∈ N0 the subgroup HN,M corresponds to the triple
(M, H 0 , 1L ), where H 0 = HN,M 0 is the following subgroup of A




j
Y

X
(bit cb−it )rt ∈ L ∀i, 1 ≤ i ≤ N,
rt ≡ 0 (mod k) .
H0 =


t=1

N
it ≡i

For all N ∈ N0 the subgroup HN,∞, corresponds to the triple (0, H 0 , 1L ).

2. For all M ∈ N and N ∈ N0 the subgroup WN,M corresponds to the triple
(M, W 0 , 1L ), with W 0 = WN,M 0 = WN,1 ∩ A. In particular, W 0 does
not depend on M . For all N ∈ N0 the subgroup WN,∞ corresponds to the
triple (0, W 0 , 1L ).
Proof. We first prove the proposition for HN,M . It is obvious that H ∩ A = H 0 .
Qj
Take g = t=1 (bit cb−it )rt · brb in HN,M . The projection of g onto Z is rb ,
which is equal to 0 (mod M ). If M is finite, since bM belongs to HN,M , the
projection of HN,M onto Z is M Z. If M = ∞, then the projection of HN,M
onto Z is 0. Finally, 1L bM belongs to HN,M as asked.
Now, for WN,M we first look at the case M = 1. Since b stabilizes (0 . . . 0), it
belongs to WN,M , the stabilizer of (0 . . . 0). Therefore, WN,1 corresponds to the
triple (1, W 0 , 1L ). For an arbitrary M , WN,M is the subgroup of WN,1 consisting
of elements with total exponent equal to 0 modulo
bi cb−i = bi−1 c̄1 b−i ,
Qj Mi.t Since
i −i
−it rt
we have expXk (b cb ) = 0 and for any g = t=1 (b cb ) · brb ∈ W1,M the
total exponent of g is precisely rb . Therefore, WN,M corresponds to the triple
(M, W 0 , 1L ) if M is finite and to the triple (0, W 0 , 1L ) if M = ∞.
Corollary 6.1.1.
1. For all M ∈ N and N ∈ N0 , the subgroup HN,M is normal if and only if
N divides M . In particular HN,∞ is normal for every N .
2. For all M ∈ N and N ∈ N0 , the subgroup WN,M is normal if and only if
N = 1.
0
0
Proof. First, we prove that HN,M
.b is always equal to HN,M
. Indeed, for all
Qj
Qj
it −it rt
it −1 −it +1 rt
cb
) . Hence, g beg = t=1 (b cb ) ∈ A we have g.b = t=1 (b
0
0
longs to HN,M
if and only if g.b belongs to HN,M
. We also trivially have that

31

0
1(b1b−1 )−1 = 1 always belongs to HN,M
. Therefore, HN,M is normal if and
M −1
0
only if g(g.b ) ∈ H for all g ∈ A.
M −1
Suppose that N does not
P divide M . Take g = c ∈ A. Then c(c.b ) =
M −M −1
c(b cb
) . The sum it ≡0 rt = 1 6≡ 0 (mod k) since k ≥ 2. Therefore
0
c(c.bM )−1 ∈
/ HN,M
, which implies that HN,M is not normal.
On
the
other
hand,
suppose now that N divides M . Then for all g =
Qj
it −it rt
(b
cb
)
∈
A,
we
have
t=1
M −1

g(g.b )

=

j
Y

it

−it rt

(b cb

t=1

) ·

j
Y

(bit −M cb−it +M )−rt

t=1

0
belongs to HN,M
.
Now, in the case of WN,M , we have (0 . . . 0, 0).cbc−1 b−1 = (01−11 · · · ± 1, 0).
Therefore, as soon as N ≥ 2, cbc−1 b−1 does not belongs to W 0 and WN,M is
not normal. For N = 1, we have (x, i).b = (x, i + 1) and (x, i).c = (x + 1, i).
Therefore,


rb ≡ 0 (mod M ) 



j


Y
j
(bit cb−it )rt brb X
W1,M = g =

rt ≡ 0 (mod k)


t=1


t=1

is a normal subgroup.

In particular, this implies that for N > 1 dividing M , the subgroups HN,M
and WN,M are not conjugate (equivalently the non-oriented Schreier graphs
are not strongly isomorphic). On the other hand, an easy check shows that
HN,1 = WN,1 . A careful look at the order of the image of c in the corresponding
action on the vertex set of S~N,M shows that for M < ∞ and N > 1, HN,M
and WN,M are nearly never conjugate (this can happen only if k divides all the

lcm(M,N )
for 1 ≤ j ≤ N − 1).
j
Proposition 6.1.1 (Part 1) and Corollary 6.1.1 imply the following.
Theorem 6.1.3. For M = N l, the spider-web graph S~N,N l is weakly isomorphic
to the Cayley graph of

⊕N
i=1 Z/kZ o Z/N lZ

where the action of Z/N lZ on ⊕N
i=1 Z/kZ is by shift, and with respect to the
generating set {bci }k−1
where
b
is
a generator of Z/N lZ and c a generator of
i=0
Z/kZ.
In particular, if we write Lk,N = Z/kZ o Z/N Z for the finite lamplighter
group, we have for N and l coprime,

Sk,N,N l ' Cay(Lk,N × Z/lZ , {(c̄r , 1)}k−1
r=0 )

which, for l = 1, gives
and for N = 1

Sk,M,M ' Cay(Lk,M , X)
Sk,1,M ' Cay(Z/kZ × Z/M Z, {(r, 1)}k−1
r=0 ).

We also have
Sk,1,∞ ' Cay(Z/kZ × Z, {(r, 1)}k−1
r=0 ).
32

~
Proof. The graph S~N,N l is weakly isomorphic to the graph Sch(L,
HN,N l , X).
Since HN,N l is normal, this graph is strongly isomorphic to the Cayley graph
of G = L/HN,N l . We know that G = hb, ci and that ck = 1 in G. Moreover,
bN l and cbN c−1 b−N belong to HN,N l and thus in G the relations bN l = 1 and
cbN = bN c are true. Therefore, G is a quotient of

L = hb, c | ck , cbN c−1 b−N , bN l , [c, bj cb−j ]; j ∈ Ni ' ⊕N
i=1 Z/kZ o Z/N lZ

where the action of Z/N lZ is by shift. We have |L| = k N ·N ·l and |G| = k N ·N l
(the number of vertices of S~N,N l ). This implies G = L.
If l and N are coprime, Z/N lZ ' Z/N Z × Z/lZ acts on ⊕N
i=1 Z/kZ, with
Z/N Z acting by shift and Z/lZ acting trivially. Hence, L ' Lk,N × Z/lZ.
Generating sets are images of {c̄r } in L.
~
Finally, S~1,∞ and Cay(Z/kZ
× Z, {(−r, −1)}k−1
r=0 ) have the same vertex set:
{1, . . . , k} × Z. Moreover, in both graphs, there is an edge from (i, s) to (j, t) if
and only if t = s + 1.

Remark 6.1.2. It is interesting to observe that the family of spider-web graphs
S~k,N,M interpolates between Cayley graphs of direct products of finite cyclic
groups and Cayley graphs of wreath products of finite cyclic groups, with the
corresponding generating sets.
Observe however that more graphs Sk,N,M can a priori be weakly isomorphic
to Cayley graphs of some finite groups than those given in Theorem 6.1.3. For
example, one can check by hand that this is the case of S2,2,3 , thought H2,2,3 is
not normal.

6.2

Transitivity

We now investigate the vertex-transitivity of spider-web graphs. We already
know from the last subsection that if N divides M the spider-web graphs are
weakly isomorphic to Cayley graphs and therefore are weakly transitive. We
will give a complete characterization of transitivity for spider-web graphs, but
before that we need a technical lemma.
Lemma 6.2.1. For any d ∈ N0 and any vertices v and w in SN,M , there is a
bijection between closed reduced paths of derangement 0 of length d with initial
vertex v and the ones with initial vertex w.
Proof. The bijection is easily seen on Sch(L, HN,M , X). Recall that we have

(x1 . . . xN , i).c̄r = (xN − r)x1 . . . xN −1 , i − 1 .

For any reduced path p with initial vertex (x1 . . . xN , i), there is a unique path
q with initial vertex (y1 . . . yN , j) with the same label l ∈ L. Since the derangement is 0, we have that
(z1 . . . zN , i).l = ((z1 + a1 ) . . . (zN + aN ), i)
for some integers ai . In particular, the end vertex of p is ((x1 + a1 ) . . . (xN +
aN ), i), while the end vertex of q is ((y1 + a1 ) . . . (yN + aN ), j). Therefore, p is
closed if and only if all the ai ’s are equal to 0, if and only if q is closed.
33

Theorem 6.2.1. For all M ∈ N and N ∈ N0 , the graphs S~N,M and SN,M
are weakly transitive (i.e. is transitive by weak automorphisms) if and only if
M ≥ N.

Proof. First, observe that any automorphism of S~N,M naturally induces an automorphism of SN,M . Therefore, it is sufficient to prove that if M ≥ N then
S~N,M is weakly transitive and that if M < N , the graph SN,M is not transitive.
~ M defined by
It is easy to check that for every M the function η on C
η(i) := i + 1 (where the addition is taken modulo M ) is an automorphism.
~ M ' S~N,M . It is even a
Therefore, T := Id ⊗η is an automorphism of S~N,1 ⊗ C
strong automorphism for every M — even for M smaller than N — since the
labeling of S~N,M comes from the labeling of S~N,1 and the fact that Id is a strong
automorphism.
We now define another function ψ on S~N,M by the following formula on
vertices:
(
(x1 . . . (xN −t + 1) . . . xN , t) if 0 ≤ t ≤ N − 1
ψ(x1 . . . xN , t) :=
(x1 . . . xN , t) else.
We define ψ on edges in the following way: the unique edge with initial vertex
(x, t) and label i is sent on the unique edge with initial vertex ψ(x, t) and label
i if t 6≡ −1 (mod M ), or on the edge with label i + 1 if t ≡ −1 (mod M ). We
claim that with this definition, ψ is a weak isomorphism
 if M ≥ N
 . To prove
that, it remains to check that for any edge e, τ ψ(e) = ψ τ (e) . Since the
definition of ψ depends on t, we have four different cases. The first is when
0 ≤ t ≤ N − 2. The second is for t = N − 1. The third when N − 1 < t < M − 1
and the last one when t = M − 1. The first, second and fourth cases are easy
computations left to the reader. In the third case, ψ acts as the identity and
there is nothing to prove. We have
T −i ψ xi T i (0 . . . 0, 0) = T −i ψ xi (0 . . . 0, i)
= (0 . . . xi . . . 0, i)
= (0 . . . xi . . . 0, 0).
Therefore, for any vertex (x1 . . . xN , t) we have


n
Y
−j xj j
i
T ·
T ψ T (0 . . . 0, 0) = (x1 . . . xN , t),
j=0

which proves the transitivity of S~N,M when M ≥ N .
Now, if M < N look at the two vertices
v = (0 . . . 0, 0)

and w = (10 . . . 0, 0)

of SN,M . By the previous lemma, there is the same number of closed paths
with derangement 0 and length M based at v and at w. Since M < N , there is
no closed path of length M starting at w with non-zero derangement. On the
other hand, there is at least one such closed path starting at v: the path where
all edges have label R0 . Therefore, there is strictly more closed paths of length
M starting at v than such paths starting at w. This implies that SN,M is not
transitive.
34

Remark 6.2.1. It is possible to demonstrate a refinement of this theorem.
Namely that if M < N , the number of orbits of S~k,N,M under its group of
N
and from above by k N −M , and
automorphisms is bounded from below by M
the number of orbits of Sk,N,M under its group of automorphisms is bounded
N
from below by max(2, 2M
) and from above by k N −M . In particular, for k and
M fixed, the number of orbits of Sk,N,M is unbounded.

6.3

Line graphs, Eulerian and Hamiltonian cycles and coverings

The family of de Bruijn graphs is well-known to enjoy some nice graph-theoretic
properties. The aim of this subsection is to verify that the family of spider-web
graphs share many of them and can thus be indeed viewed as a natural extension
of de Bruijn graphs.
Proposition 6.3.1. For all M ∈ N and N ∈ N0 , the spider-web graph S~N +1,M
is (weakly) isomorphic to the line graph of S~N,M .
Proof. This follows from the same result for de Bruijn graphs (Lemma 4.1.1),
~N ⊗ C
~ M , Lemma 3.2 and the fact
the fact that S~N,M is the tensor product B
~ M is its own line graph.
that C
Proposition 6.3.2. For all M ∈ N and N ∈ N0 , the spider-web graph S~N,M
is Eulerian (there exists a closed path p consisting of edges of S~N,M that visits
each edge exactly once) and Hamiltonian (there exists a closed path that visits
each vertex exactly once)
Proof. The directed graph S~N,M is finite, connected and for every vertex v in
S~N,M the number of outgoing edges is equal to the number of ingoing edges.
Therefore, S~N,M is Eulerian.
For N ≥ 1, the graph S~N,M is isomorphic to the line graph of S~N −1,M . This
line graph is Hamiltonian since S~N −1,M is Eulerian. Finally, S~0,M is a “thick”
oriented circle: the vertex set is M and for every vertex i there is k edges from
i to i + 1. This graph is obviously Hamiltonian.
We proved that S~N,M is Eulerian and Hamiltonian as an oriented graph.
That is, the closed path in question consists only of edges of S~N,M . This trivially implies that SN,M is Eulerian and Hamiltonian. Indeed, for an oriented
~ being Eulerian (or Hamiltonian) as an oriented graph is a stronger
graph Θ,
~ being Eulerian (or Hamiltonian) as a non-oriented graph. Fiproperty that Θ
nally, we generalize Corollary 4.4.1 and show that spider-web graphs form towers
of graphs coverings, both in N and, in a certain sense, in M .
Proposition 6.3.3. For all M ∈ N and N ∈ N, the oriented graph S~N,M
(weakly) covers S~N −1,M .
For every i ∈ N, the oriented graph S~N,iM (weakly) covers S~N,M .
~N +1 covers B
~N and it is easily seen
Proof. By Corollary 4.4.1, we know that B
~
~
that CiM covers CM . A simple application of Lemma 3.1 gives the desired
result.
35

~1 →∆
~ 2 naturally induces a
Note that any covering of oriented graphs φ : ∆
covering between the underlying graphs.

References
[1] Ajit C. Balram and Deepak Dhar. Non-perturbative corrections to meanfield critical behavior: the spherical model on a spider-web graph. J. Phys.
A, 45(12):125006, 14, 2012.
[2] Laurent Bartholdi and Wolfgang Woess.
Spectral computations on
lamplighter groups and Diestel-Leader graphs. J. Fourier Anal. Appl.,
11(2):175–202, 2005.
[3] Itai Benjamini and Oded Schramm. Recurrence of distributional limits of
finite planar graphs. Electron. J. Probab., 6:no. 23, 13 pp. (electronic),
2001.
[4] Phillip E C Compeau, Pavel A Pevzner, and Glenn Tesler. How to apply
de Bruijn graphs to genome assembly. Nat Biotech, 29(11):987–991, 2011.
[5] Charles Delorme and Jean-Pierre Tillich. The spectrum of de Bruijn and
Kautz graphs. European J. Combin., 19(3):307–319, 1998.
[6] Warren Dicks and Thomas Schick. The spectral measure of certain elements
of the complex group ring of a wreath product. Geom. Dedicata, 93:121–
137, 2002.
[7] Gábor Elek. On the analytic zero divisor conjecture of Linnell. Bull. London
Math. Soc., 35(2):236–238, 2003.
[8] Rostislav Grigorchuk, Daniel Lenz, and Nagnibeda Tatiana. Spectra of
schreier graphs of Grigorchuk’s group and Schroedinger operators with aperiodic order. arXiv:1412.6822.
[9] Rostislav Grigorchuk, Daniel Lenz, and Nagnibeda Tatiana. Schreier graphs
of Grigorchuk’s group and a subshift associated to a non-primitive substitution. In T. Ceccherini-Silberstein, M. Salvatori, and E. Sava-Huss, editors,
Groups, Graphs, and Random Walks. London Mathematical Society Lecture Note Series, Cambridge University Press, to appear (2016).
[10] Rostislav I. Grigorchuk and Rostyslav Kravchenko. On the lattice of subgroups of the lamplighter group. Internat. J. Algebra Comput., 24(6):837–
877, 2014.
[11] Rostislav I. Grigorchuk, Volodymyr V. Nekrashevich, and Vitaliy I.
Sushchanskiı̆. Automata, dynamical systems, and groups. Tr. Mat. Inst.
Steklova, 231(Din. Sist., Avtom. i Beskon. Gruppy):134–214, 2000.
[12] Rostislav I. Grigorchuk and Andrzej Żuk. The lamplighter group as a group
generated by a 2-state automaton, and its spectrum. Geom. Dedicata, 87(13):209–244, 2001.
[13] Nobuichi Ikeno. A limit on crosspoint numbers. IRE Trans. Inform. Theory,
5:18–196, 1959.
36

[14] Wilfried Imrich and Sandi Klavžar. Product graphs. Wiley-Interscience
Series in Discrete Mathematics and Optimization. Wiley-Interscience, New
York, 2000. Structure and recognition, With a foreword by Peter Winkler.
[15] Mark Kambites, Pedro V. Silva, and Benjamin Steinberg. The spectra of
lamplighter groups and Cayley machines. Geom. Dedicata, 120:193–227,
2006.
[16] Paul-Henry Leemann. Limits of Rauzy graphs and horocyclic products of
trees, in preparation.
[17] Volodymyr Nekrashevych. Self-similar groups, volume 117 of Mathematical
Surveys and Monographs. American Mathematical Society, Providence, RI,
2005.
[18] Nicholas Pippenger. The blocking probability of spider-web networks. Random Structures Algorithms, 2(2):121–149, 1991.
[19] Nicholas Pippenger. The asymptotic optimality of spider-web networks.
Discrete Appl. Math., 37/38:437–450, 1992.
[20] Nicholas Pippenger. The linking probability of deep spider-web networks.
SIAM J. Discrete Math., 20(1):143–159 (electronic), 2006.
[21] Yu. V. Prohorov. Convergence of random processes and limit theorems in
probability theory. Teor. Veroyatnost. i Primenen., 1:177–238, 1956.
[22] Jean-Pierre Serre. Arbres, amalgames, SL2 . Société Mathématique de
France, Paris, 1977. Avec un sommaire anglais, Rédigé avec la collaboration
de Hyman Bass, Astérisque, No. 46.
[23] Pedro V. Silva and Benjamin Steinberg. On a class of automata groups generalizing lamplighter groups. Internat. J. Algebra Comput., 15(5-6):1213–
1234, 2005.
[24] Wolfgang Woess. Lamplighters, Diestel-Leader graphs, random walks, and
harmonic functions. Combin. Probab. Comput., 14(3):415–433, 2005.
[25] Fu Ji Zhang and Guo Ning Lin. On the de Bruijn-Good graphs. Acta Math.
Sinica, 30(2):195–205, 1987.

37

