Exercise 15, § 2

Let $G = (S,F, o, t, \iota )$ be a graph (TA, II, p. 155, déf. 1). Suppose that G is connected, that S is countable and that S has at least two elements. For every $x\in S$, denote by $v(x)$ the number of edges of G of which $x$ is an endpoint; we have $v(x)\geqslant 1$ for every $x\in S$, and suppose that $v(x)$ is finite for every $x\in S$. For all $x$ and $y$ in S, denote by $a(x, y)$ the number of arrows in G with endpoints $x$ and $y$. Suppose that $a(x, y)$ is finite for every $(x, y)\in S^2$.

Define a measure $\mu$ on S by $\mu(\{x\}) =v(x)$ for every $x\in S$. The measure $\mu$ is positive. Denote by $\mathscr{F}(G)$ the vector space of functions on S with complex values. Denote by $\widetilde{M}_G$ the endomorphism of $\mathscr{F}(G)$ such that

$y$

for every $\varphi \in \mathscr{F}(G)$ and every $x\in S$ (“Markov operator”).

a) The endomorphism $\widetilde{M}_G$ defines by passing to the subspaces an endomorphism $M_G$ of $L^2_{\mathbf{C}}(S, \mu)$.

b) The endomorphism $M_G$ is self-adjoint. It satisfies

$(x,y)\in S^2$ $\langle \varphi |1 + M_G(\varphi )\rangle =\frac{1}{2}\sum a(x, y)|\varphi (x) +\varphi (y)|^2$

$(x,y)\in S^2$ for every $\varphi \in L^2(S, \mu)$. Moreover, we have $-1\leqslant M_G\leqslant 1$.

c) Let $d\geqslant 1$ be an integer and suppose that G is the Cayley graph of $\mathbf{Z}^d$ relative to the set $\{e_i\}$, where $(e_i)$ is the canonical basis of $\mathbf{Z}^d$ (TA, II, p. 221, exercise 7). The spectral radius $\varrho (M_G)$ of $M_G$ is equal to 1.

d) Let $d\geqslant 3$ be an integer. Suppose that G is an infinite $d$-regular tree (TA, II, p. 157), that is to say an infinite tree in which every vertex has $d$ neighbors. Let $x_0$ be a fixed vertex of G. For every $\lambda \in \mathbf{C}$, there exists a unique function $\varphi_{\lambda}: S\rightarrow \mathbf{C}$ such that $\varphi_{\lambda}(x_0) = 1$ and $\widetilde{M}_G(\varphi_{\lambda}) =\lambda \varphi_{\lambda}$. Moreover, for every $x\in S$, the value of $\varphi_{\lambda}$ at $x$ depends only on the distance from $x$ to $x_0($cf. TA, II, p. 222, exercise 10).

ede Kesten »). In particular, we have a) The spectrum of $M_G$ is the interval $[\varrho (M_G-) = 2$2 $d-\surd d1/d,-12/d.d-1/d]$ (“theorem