\chapter{Examples and applications}
\label{sec:examples}

\headerquote{The art of doing mathematics consists in finding that special case which contains all the germs of generality}{---~D.~Hilbert}

\section{Finite graphs}
\label{sec:finite-graphs}

\subsection{Elementary examples}
\label{sec:elementary-examples}

\begin{exm}\label{exm:linear-network}
  Consider a ``linear'' \ERN consisting of several resistors connected in series with resistances $\ohm_i = \cond_i^{-1}$ as indicated:
  \[\xymatrix{
      \ga = x_0 \ar[r]^{\hstr[3] \ohm_1}
      & x_1 \ar[r]^{\ohm_2}
      & x_2 \ar[r]^{\ohm_3}
      & x_3 \ar[r]^{\ohm_4}
      & \dots \ar[r] ^{\ohm_n \hstr[2]}
      & x_n =\gw
    }\]
  Construct a dipole $v \in \Pot(\ga,\gw)$ on this network as follows. Let $v(x_0) = V$ be fixed. Then determine $v(x_1)$ via \eqref{eqn:def:dipole}:
  \linenopax
  \begin{align*}
    \Lap v(x_0) = \tfrac1{\ohm_1}(V-v(x_1))=1 &\implies v(x_1)=V-\ohm_1,\\
    \Lap v(x_1) = \sum_{k=1}^2 \tfrac1{\ohm_k}(v(x_{k-1})-v(x_k))=0 &\implies v(x_2)=V-\ohm_1-\ohm_2,
  \end{align*}
  and so forth. Three things to notice about this extremely elementary example are (i) $v$ is fixed by its value at one point and any other dipole on this graph can differ only by a constant, (ii) we recover the basic fact of electrical theory that the voltage drop across resistors in series is just the sum of the resistances, and (iii) all current flows are induced (this is not true of more general graphs).

  \version{}{\marginpar{What does this construction illustrate?}}
  Consider the basis $\{e_0,e_1,\dots,e_N\}$, where $e_k = \gd_{x_k}$, the unit Dirac mass at $k$. The Laplace operator for this model has the matrix
  \begin{equation}\label{exm:finite-linear-model}
    \Lap =
    \left[\begin{array}{rrrrrr}
      1 & -1 & 0 & \dots && 0 \\
      -1 & 2 & -1 & \dots && 0 \\
      0 & -1 & 2 & \dots && 0 \\
      \vdots & && \ddots \\
      0 & &\dots & -1 & 2 & -1 \\
      0 & &\dots & 0 & -1 & 1
    \end{array}\right].
  \end{equation}
  One may obtain a unitary representation on $\ell^2(\bZ_N)$ by using the diagonal matrix $U(\gz) = \diag(1,\gz,\gz^2,\dots,\gz^N)$, where $\gz := e^{2\gp\ii/(N+1)}$ is a primitive \nth[(N+1)] root of 1, so that $\gz^{-1}=\bar \gz$. It is easy to check that for any matrix $M \in \sM_{N+1}(\bC)$, one has $[U(\gz) M U(\gz)^\ad]_{j,k} = \gz^{j-k} [M]_{j,k}$. Then define
  \linenopax
  \begin{align*}\label{eqn:unitary-zeta-Lap-defined}
    \Lap(\gz)
    :=& U(\gz) \Lap U(\gz)^\ad,
  \end{align*}
  and see that $\Lap(\gz) = \Cond - U(\gz) \Trans U(\gz)^\ad$. It is clear that $\spec \Lap = \spec\Lap(\gz)$, because
  \linenopax
  \begin{align*}
    \Lap v = \gl v
    \qq\iff\qq
    \Lap(\gz) [U(\gz) v] = \gl [U(\gz) v].
  \end{align*}
  Decompose the transfer operator into the sum of two shifts, so that $\Trans = M_+ + M_-$, where $M_+$ has ones below the main diagonal and zeros elsewhere, and $M_-$ has ones above the diagonal and zeros elsewhere. Then we have $U(\gz) M_+ U(\gz)^\ad = \gz M_+$ and $U(\gz) M_- U(\gz)^\ad = \bar\gz M_-$ and $M_- = M_+^\ad$. By induction, the characteristic polynomial can be written
  \linenopax
  \begin{align*}
    p_n(x) = \det(x\id - \Trans_n) = x p_{n-1}(x) - p_{n-2}(x),
  \end{align*}
  with $p_1=x, p_2=x^2-1,p_3=x^3-2x,p_4=x^4-3x^2+1$, and corresponding Perron-Frobenius eigenvalues $\gl_1=0, \gl_2 = 1, \gl_3 = \sqrt2, \gl_4 = \phi = \frac12(1+\sqrt5)$.
  \linenopax
  \begin{align*}
    \spec \Lap_2 = \{0,1\}, \q
    \spec \Lap_3 = \{0,1,3\}, \q
    \spec \Lap_4 = \{0,2,2\pm\sqrt2\}.
  \end{align*}
\end{exm}

\begin{exm}\label{exm:one-small-cycle-network}
  The correspondence $\Pot(\ga,\gw) \to \Flo(\ga,\gw)$ described in Lemma~\ref{thm:potential-induces-current} is not bijective, i.e., the converse to the theorem is false, as can be seen from the following example. Consider the following electrical  network with resistances $\ohm_i = \cond_i^{-1}$.
  \linenopax
    \begin{align*}
    \xymatrix{
      *+[l]{\ga = x_0} \ar[r]^{\ohm_1} \ar[d]^{\ohm_2} & x_1 \ar[d]^{\ohm_3} \\
      x_2 \ar[r]^{\ohm_4} & *+[r]{x_3 = \gw}
    }
  \end{align*}
  One can verify that the following gives a current flow $\curr = \curr_t$ on the graph for any $t \in [0,1]$:
  \linenopax
    \begin{align*}
    \xymatrix{
      x_0 \ar[r]_t \ar[d]_{1-t} & x_1 \ar[d]_t \\
      x_2 \ar[r]_{1-t} & x_3
    }
  \end{align*}
  In fact, there are many flows on this network; let $\charfn{\cycle}$ be the characteristic function of the cycle $\cycle = (x_0, x_1, x_3, x_2)$
  \[\cycle =
    \begin{gathered}
    \xymatrix{
      x_0 \ar[r] & x_1 \ar[d] \\
      x_2 \ar[u] & x_3 \ar[l]
    }
    \end{gathered}
  \]
  so that $\charfn{\cycle}(e) = 1$ for each $e \in \{e_1=(x_0, x_1), e_2=(x_1, x_2), e_3=(x_2, x_3), e_4=(x_3, x_0)\}$. Then $\curr_t + \ge \charfn{\cycle}$ will be a flow for any $\ge \in \bR$. (Although this formulation seems more awkward than simply allowing $t$ to take any value in \bR, it is easier to work with characteristic functions of cycles when there are many cycles in the network.) However, there will be only one value of $t$ and \ge for which the above flow corresponds to a potential function, and that potential function is the following:
  \linenopax
  \begin{align*}
    \xymatrix{
      V \ar[r] \ar[d]
        & V - \frac{\ohm_2 + \ohm_4}{\sum_{k=1}^4 \ohm_k}\ohm_1 \ar[d] \\
      V - \frac{\ohm_1 + \ohm_3}{\sum_{k=1}^4 \ohm_k}\ohm_2 \ar[r]
        & V - \frac{(\ohm_1 + \ohm_3)(\ohm_2 + \ohm_4)}{\sum_{k=1}^4 \ohm_k}
    }
  \end{align*}
  This is the potential function which ``balances'' the flow around both sides of the square; it can be computed as in the previous example. These ideas are given formally in Theorem~\ref{thm:minimal-flows-are-induced-by-minimizers}.
\end{exm}

\begin{exm}[Finite cyclic model]\label{exm:finite-cyclic-model}
  In this case, let $\Graph_N$ have vertices given by $x_k = e^{2\gp\ii k/N}$ for $k=1,2,\dots,N$, with edges connecting each vertex to its two nearest neighbours. For example, when $N=9$,\\
  \begin{center}
    $\Graph_9$ \qq \xy \xygraph{[rrr] !P9"C"{~={42} ~*{x_{\xypolynode}}} }\endxy $=x_0$
  \end{center}
  In this case, using the same basis $\{e_0,e_1,\dots,e_N\}$, as in Example~\ref{exm:linear-network}, the Laplace operator for this model has the matrix
  \begin{equation}\label{eqn:exm:finite-cyclic-model}
    \Lap =
    \left[\begin{array}{rrrrrrrr}
      2 & -1 & 0 & \dots  & 0 & -1 \\
      -1 & 2 & -1 & \dots  & 0 & 0 \\
      0 & -1 & 2 & \dots  & 0 & 0 \\
      \vdots & && \ddots \\
      0 & 0 & 0 & \dots  & 2 & -1 \\
      -1 & 0 & 0 & \dots  & -1 & 2
    \end{array}\right].
  \end{equation}
  The Fourier transform $\sF$ is a spectral transform of \Lap that shows it to be unitarily equivalent to multiplication by $4\sin^2\left(\frac{\gp k}{N}\right)$.


  \begin{lemma}\label{thm:Lap_N-is-4sin2-etc}
    For $S := \sF^\ad \Lap \sF$ and $v \in \HE$, one has
    \linenopax
    \begin{align*}
      (Sv)(z) = (2-z-z^{-1})v(z), \qq z=\ga^k, k=0,1,2,\dots,N.
    \end{align*}
    \begin{proof}
      Denote $v_k=v(k)$ and consider the Fourier transform $\sF:\{v_k\} \mapsto \sum_{k \in \bZ_N} v_k z^k$: 
      \linenopax
      \begin{align*}
        \sF(\Lap v)(z) 
        &= \sum_{k \in \bZ_N} (2v_k - v_{k-1} - v_{k+1}) z^k \\
        &= 2\sum_{k \in \bZ_N} v_k z^k - \sum_{k \in \bZ_N} v_{k-1} z^k - \sum_{k \in \bZ_N} v_{k+1} z^k \\
        &= (2 - z - z^{-1}) \sum_{k \in \bZ_N} v_k z^k.
      \end{align*}
      This shows $\sF(\Lap v)(z) = (2-z-z^{-1})\sF(v)(z)$, so that $S$ is multiplication by $(2-z-z^{-1})$. 
    \end{proof}
  \end{lemma}

  \pgap

  In this case, $\Lap = \id - \Trans$ with $\Cond = 2\id$, so that \Cond and \Trans commute. Additionally, \Trans is the sum of two shifts and so corresponds to multiplication by $z+z^{-1} = 2\cos \gq$ on $\ell^2(\verts_N)$, where $\gq = \frac{2\gp k}N$. Consequently, $\spec \Trans_N = 2 \cos \left(\frac{2\gp k}N\right)$ and the Perron-Frobenius eigenvalue of $\Trans_N$ is $\gl_{PF}=2$, which occurs for $k=0$ and has eigenfunction $v_{PF} = [1,1,\dots,1]$. Observe that $\Lap_N$ commutes with the cyclic shift. The eigenfunctions of the shift are $v = [1,\gl,\gl^2,\dots,\gl^{N-1}]$, where $\gl \in \verts$, and hence these are the other eigenfunctions of $\Trans_N$.

  \begin{prop}
    The spectrum of $\Lap_N$ is given by
    \linenopax
    \begin{align*}
      \spec \Lap_N = \{2\left(1-\cos \left(\tfrac{2\gp k}N\right) \right)\suth k \in \bZ_N\}.
    \end{align*}
    \begin{proof}
      Let $U$ be the cyclic shift in the positive direction, i.e., $U$ has the matrix
      \linenopax
      \begin{align*}
        U =
        \left[\begin{array}{cccccc}
          0 & &&&1\\ 1 & 0 \\ & 1 & 0 \\ &&\ddots& \ddots \\ &&&1 &0
        \end{array}\right].
      \end{align*}
      The $U$ and $\Lap_N$ commute. For $n \in \bZ_n$, the Fourier transform is
      \linenopax
      \begin{align*}
        \hat v(n) = \frac1N \sum_{z \in \verts_N} z^{-n} v(z),
        \q\text{so}\q
        x_k \mapsto v(n) = \sum_{n \in \bZ_N} z^n \hat v(n).
        &\qedhere
      \end{align*}
      \version{}{\marginpar{Some comment here about a Hadamard matrix?}}
    \end{proof}
  \end{prop}
  \version{}{\marginpar{At this point, I can no longer follow the notes. What is the main point? The Fourier transform diagonalizes \Lap, but what is the application here?}}
  For $k \in \{1,2,\dots,N-1\}$, one can find $v \in \Pot(k,0)$ as follows: ``ground'' the graph with $v(0)=0$ and consider
  \linenopax
    \begin{align*}
    \xymatrix{
    \dots \ar[r]_\ga & x_1 \ar[r]_\ga & x_0=x_N & x_{N-1} \ar[l]^{1-\ga} & \dots \ar[l]^{1-\ga} & x_k \ar[l]^{1-\ga} \ar[r]_\ga & \dots
    }
  \end{align*}
  The cycle condition (the net drop of voltage around any closed cycle must be 0) yields $v(k)-v(0) = k\ga = (N-k)(1-\ga)$, and hence $\ga = \tfrac{N-k}N$. This gives $v(k) = \tfrac{k(N-k)}{N}$ and we have
  \linenopax
  \begin{align*}
    \Lap v(j) = \gd_k - \gd_0 =
    \begin{cases}
      -\tfrac{k}{N} - \tfrac{N-k}{N} = -1, &j=0 \\
      \tfrac{k}{N} - \tfrac{k}{N} = 0, &0 < j < k \\
      \tfrac{k}{N} + \tfrac{N-k}{N} = 1, &j=k \\
      \tfrac{N-k}{N} - \tfrac{N-k}{N} = 0, &k < j \leq N-1.
    \end{cases}
  \end{align*}
  This additionally shows that if the shortest path from $x$ to $y$ has length $k$, then $R(x,y) = k\frac{N-k}N < k$. Of course, there is an easier way to get $R(x,y)$. Since there are only two paths $\cpath_1,\cpath_2$ from $x$ to $y$, the laws for resistors connected in serial and parallel indicate that the entire network can be replaced by a single edge $(x,y)$ with resistance $(\ohm(\cpath_1)^{-1} + \ohm(\cpath_1)^{-1})^{-1}$. In the case of constant resistance $\ohm \equiv 1$, this becomes
  \linenopax
  \begin{align*}
    (\ohm(\cpath_1)^{-1} + \ohm(\cpath_1)^{-1})^{-1}
     = \left(\frac1k + \frac1{N-k}\right)^{-1}
     = \left(\frac{(N-k)+k}{k(N-k)}\right)^{-1}
     = k\frac{N-k}N.
  \end{align*}
\end{exm}

  \begin{figure}
    \centering
    \scalebox{0.90}{\includegraphics{periodic-potential.pdf}}
    \caption{\captionsize The solution $v$ as represented on \bR.}
    \label{fig:periodic-potential}
  \end{figure}


\begin{exm}\label{exm:edge-deletion-network}
  Next, it is illuminating to see how things change when edges are removed from the network. 
  
  \version{}{\marginpar{Add proof}
\begin{lemma}[Powers' inequality]
  \label{thm:Powers-inequality}
  Suppose \Graph is finite and $H \ci \Graph$ is obtained by removing the edges $\{e_i\}_{i=1}^n$. Then 
  \begin{align}\label{eqn:Powers-inequality}
    R_G(x,y) \leq R_H(x,y) \leq \frac{1}{\ge^2} R_G(x,y), 
  \end{align}
  for $\ge := 1- \sum_{i=1}^n |\curr(e_i)|$.
\end{lemma}
}

Consider the following example, where $\cond = \one$ and the currents are as indicated, and the second network is obtained from the first by deleting two edges, as indicated:
  \linenopax
  \begin{align*}
    \xymatrix{
      &*+[l]{\ga = x_0} \ar[dl]^{\frac{2}{11}} \ar[dd]^{\frac{4}{11}} \ar[r]^{\frac{5}{11}} & x_1 \ar[dd]^{\frac{5}{11}} \\
       x_2 \ar[dr]^{\frac{2}{11}} \\
      & x_3 \ar[r]^{\frac{6}{11}} & *+[r]{x_4 = \gw} \\
      &\hstr[5]\curr_0
    }
    \hstr[5]
    \xymatrix{
      & *+[l]{\ga = x_0} \ar[dd]^{\frac12} \ar[r]^{\frac12} & x_1 \ar[dd]^{\frac12} \\
      \\
      & x_3 \ar[r]^{\frac12} & *+[r]{x_4 = \gw} \\
      &\hstr[5]\curr_1
    }
  \end{align*}
  The dissipations are
  $R_0(\ga,\gw) = \diss(\curr_0) = \frac{10}{11}$ and $R_1(\ga,\gw) = \diss(\curr_1) = 1$.
  The set of paths from \ga to \gw that don't pass through the deleted edges contains
  only $\cpath_1 = (\ga,x_1,\gw)$ and $\cpath_2 = (\ga,x_3,\gw)$. Then
  \linenopax
  \begin{align*}
    \ge = \sum_{\cpath \in Q \less W} \prob(\cpath) = \prob(\cpath_1) + \prob(\cpath_2) = \frac{4}{11} + \frac{5}{11} = \frac9{11},
  \end{align*}
  \version{}{\marginpar{Must include!}}
  and Powers' inequality gives
  \linenopax
  \begin{align*}
    R_0(\ga,\gw) &\leq R_1(\ga,\gw) \leq \ge^{-2} R_0(\ga,\gw) \\
    \frac{10}{11} &\leq 1 \leq \frac{121}{81} \cdot \frac{10}{11} = \frac{110}{81}.
  \end{align*}
\end{exm}


\section{Infinite graphs}
\label{sec:infinite-graphs}

\begin{exm}\label{exm:edge-boundary}
  Define the projections
\linenopax
\begin{equation}\label{eqn:exhaustion-restriction-projections}
  B_n = \charfn{\Graph_n}, \qq B_n^\perp = \charfn{\Graph \less \Graph_n} = \charfn{\Graph_n^\complement}.
\end{equation}
Let us denote the \emph{edge boundary} between $\Graph_n$ and $\Graph_{n+1}$ by
\begin{equation}\label{eqn:nth-edge-boundary}
  Edge_n := \{e=(x,y)\in\edges \suth y \in \verts_n, x \in \verts \less \verts_n\}.
\end{equation}
We now consider the behavior of $\| B_n^\perp \Lap B_n\|$, where the norm is with respect to operators $\ell^2(\cond) \to \ell^2(\cond)$.
\end{exm}

\begin{lemma}\label{thm:edge-boundary-bound}
  For $C_n := \sup\{\sum_{y \nbr x} \cond_{xy}^2 \suth (x,y) \in Edge_n\}$,
  \begin{equation}\label{eqn:lem:edge-boundary-bound}
    \|B_n^\perp \Lap B_n\| \leq C_n.
  \end{equation}
  \begin{proof}
    Let $v \in \ell^2(\cond)$ and $x \in (\verts_n)^\complement$.
    Then
    \linenopax
    \begin{align*}
      (B_n^\perp \Lap B_n v)(x)
      &= \charfn{\Graph^\complement}(x) \sum_{y \nbr x} \cond_{xy} \left(\cancel{\charfn{\Graph_n} v(x)} - \charfn{\Graph_n} v(y)\right) \\
      &= - \negsp[15] \sum_{(x,y) \in Edge_n} \negsp[10] \cond_{xy} v(y), \q x \in (\verts_n)^\complement.
    \end{align*}
    Now summing over all $x \in (\verts_n)^\complement$, and hence over all edges in $Edge_n$,
    \linenopax
    \begin{align*}
      \|B_n^\perp \Lap B_n v\|_\cond^2
      &= \left|\sum_{(x,y) \in Edge_n} \negsp[20] \cond_{xy} v(y) \right|^2 \negsp[10]
      \leq \sum_{y \in \verts_n} |v(y)|^2 \negsp[10]
         \sum_{\substack{x \in (\verts_n)^\complement \\ y \nbr x}} |\cond_{xy}|^2
      \leq C_n^2 \|v\|_\cond^2,
    \end{align*}
    and hence $\|B_n^\perp \Lap B_n\|_\cond \leq C_n$.
  \end{proof}
\end{lemma}

\begin{prop}\label{thm:edge-boundary-O(n2)}
\version{}{\marginpar{Can Prop.~\ref{thm:edge-boundary-O(n2)} be applied  to the infinite Sierpinski lattice? Must compute ...}}
  If the estimate
  \begin{equation}\label{eqn:edge-boundary-O(n2)}
    \| B_n^\perp \Lap B_n\| = O(n^2), \q \text{as } n \to \iy,
  \end{equation}
  is satisfied, then \Lap has no eigenvectors at \iy.
  \begin{proof}
    Since \Lap is semibounded, this follows from \cite{Jor78}. (The reader may find information in \cite{Jor76} and \cite{Jor77} regarding the general Hermitian case.)
  \end{proof}
\end{prop}


\begin{exm}[One-sided ladder model]\label{exm:one-sided-ladder-model}
  The elementary ladder models help explain the effects of adding to the network, when the new portions added to the graph are somewhat ``peripheral'' to the original graph. Also, they provide an easy example of an infinite network in which a shortest path (see Remark~\ref{rem:shortest-path-metric}) may not exist, and then illustrate a technique for understanding what happens on a finite subgraph of interest which is embedded in an infinite graph.

Consider a graph which appears as a sideways ladder with $n$ rungs extending to the right:
  \begin{equation}\label{eqn:exm:one-sided-ladder-model}
    \xymatrix{
    *+[l]{\ga = x_0} \ar[r] \ar[d]
      & x_1 \ar[r] \ar[d] & x_2 \ar[r] \ar[d] & x_3 \ar[r] \ar[d]
      &\dots x_n \ar[d] \\
    *+[l]{\gw = y_0} & y_1 \ar[l] & y_2 \ar[l] & y_3 \ar[l] &\dots y_n \ar[l]
    }
  \end{equation}

  \version{}{\marginpar{Must add ...}
  We wish to find the minimizing current running down the leftmost edge, i.e., insert one amp at the top left corner and withdraw one amp from the bottom left corner.
 How does the flow respond as $n$ increases, and what happens as $n \to\iy$? \\

  [[To be added]]
  }
  
  The one-sided ladder model furnishes a situation where no shortest path exists, as mentioned in Remark~\ref{rem:shortest-path-metric}, if the resistances are defined as follows:
  \begin{equation}\label{eqn:exm:one-sided-ladder-model-no-shortest-path}
    \xymatrix{
    *+[l]{\ga = x_0} \ar@{-}[r]_{\frac14} \ar@{-}[d]_1
      & x_1 \ar@{-}[r]_{\frac1{16}} \ar@{-}[d]_{\frac1{4}} & x_2 \ar@{-}[r]_{\frac1{64}} \ar@{-}[d]_{\frac1{16}} & x_3 \ar@{-}[r] \ar@{-}[d]_{\frac1{64}}
      &\dots \ar@{-}[r]_{\frac1{4^n}} & x_n \ar@{-}[d]_{\frac1{4^n}} \\
    *+[l]{\gw = y_0} & y_1 \ar@{-}[l]_{\frac14} & y_2 \ar@{-}[l]_{\frac1{16}} & y_3 \ar@{-}[l]_{\frac1{64}} &\dots  \ar@{-}[l] & y_n \ar@{-}[l]_{\frac1{4^n}}
    }
  \end{equation}
  To find a path from \ga to \gw with minimal distance, one is led to consider paths stretching ever further off towards infinity. It is easy to see that the shortest path metric gives
  \linenopax
  \begin{align*}
    \distmin(\ga,\gw) = \lim \left[2\left(\frac14 + \frac1{16} + \dots + \frac1{4^n}\right) + \frac1{4^n}\right] = \frac23,
  \end{align*}
  but there is no $\cpath \in \Paths_{\ga,\gw}$ for which $\prob(\cpath) = \frac23$.
  Note that the Powers bound \eqref{eqn:def:power-bound} is violated, as $\gm(x_n) = 4^n+4^n+4^{n+1} \to \iy$.
\end{exm}


\begin{exm}[One-sided infinite ladder network]\label{exm:a,b-ladder}
  Consider the same ladder network as above, except now let the horizontal conductances grow geometrically, and let the vertical conducatances decay geometrically. More precisely, fix two positive numbers $\ga > 1 > \gb > 0$. Define the horizontal conductances between nearest neighbours by $\cond_{x_n, x_{n-1}} = \cond_{y_n, y_{n-1}} = \ga^n$, and define the vertical conductance of the ``rungs'' of the ladder by $\cond_{x_n,y_n} = \gb^n$:
  \linenopax
  \begin{equation}\label{eqn:exm:one-sided-ladder-model}
    \xymatrix{
    *+[l]{x_0} \ar@{-}[r]^{\ga} \ar@{-}[d]_{1}
      &  x_1 \ar@{-}[r]^{\ga^2} \ar@{-}[d]_{\gb} 
      &  x_2 \ar@{-}[r]^{\ga^3} \ar@{-}[d]_{\gb^2} 
      &  x_3 \ar@{-}[r]^{\ga^4} \ar@{-}[d]_{\gb^3}
      &\dots \ar@{-}[r]^{\ga^n}
      &  x_n \ar@{-}[r]^{\ga^{n+1}} \ar@{-}[d]_{\gb^n} & \dots \\
    *+[l]{y_0}\ar@{-}[r]^{\ga} 
      &  y_1 \ar@{-}[r]^{\ga^2} 
      &  y_2 \ar@{-}[r]^{\ga^3} 
      &  y_3 \ar@{-}[r]^{\ga^4} 
      &\dots \ar@{-}[r]^{\ga^n}
      &  y_n \ar@{-}[r]^{\ga^{n+1}} 
      & \dots
    }
  \end{equation}
  
  This network was suggested to us by Agelos Georgakopoulos as an example of a one-ended network with nontrivial \Harm. The function $u$ constructed below is the first example of an explicitly computed nonconstant harmonic function of finite energy on a graph with one end (existence of such a phenomenon was first proved in \cite{CaW92}). Numerical experiments indicate that this function is also bounded (and even that the sequences $\{u(x_n)\}_{n=0}^\iy$ and $\{u(y_n)\}_{n=0}^\iy$ actually converge very quickly), but we have not yet been able to prove this. Numerical evidence also suggests that \Lap is not essentially self-adjoint on this network, but we have not yet proved this, either. However, compare with the defect on the geometric integers discussed in \S\ref{sec:defect-on-geometric-integers}.
  
  This graph clearly has one end. We will show that such a network has nontrivial resistance boundary if and only if $\ga > 1$ and in this case, the boundary consists of one point for $\gb=1$, and two points for \gb such that $(1 + \frac1\ga)^2 < \ga / \gb^2$. It will be made clear that the paths $\cpath_x=(x_1,x_2,x_3,\dots)$ and $\cpath_y=(y_1,y_2,y_3,\dots)$ are equivalent in the sense of Definition~\ref{def:harmonic-equivalence-of-paths} if and only if $\gb = 1$.
  
  For presenting the construction of $u$, choose $\gb < 1$ satisfying $4\gb^2 < \ga$ (at the end of the construction, we explain how to adapt the proof for the less restrictive condition $(1 + \frac1\ga)^2 < \ga/\gb^2$). We now construct a nonconstant $u \in \Harm$ with $u(x_0) = 0$ and $u(y_0)=-1$. If we consider the flow induced by $u$, the amount of current flowing through one edge determines $u$ completely (up to a constant). Once it is clear that there are two boundary points 
  in this case, it is clear that specifying the value of $u$ at one 
  (and grounding the other) 
  determines $u$ completely.
  
  Due to the symmetry of the graph, we may abuse notation and write $n$ for $x_n$ or $y_n$, and $\check n$ for the vertex ``across the rung'' from $n$. For a function $u$ on the ladder, denote the horizontal increments and the vertical increments by  
  \linenopax
  \begin{align*}
    \gd u(n) := u(n+1) - u(n)
    \qq\text{and}\qq
    \gs u(n) := u(n) - u(\check n),
  \end{align*}
  respectively. 
  Thus, for $n \geq 1$, we can express the equation $\Lap u(n) = 0$ by
  \linenopax
  \begin{align*}
    \Lap u(n) = \ga^n \gd u(n-1) - \ga^{n+1} \gd u(n) + \gb^n \gs u(n) = 0,
  \end{align*}
  which is equivalent to 
  \linenopax
  \begin{align*}
    \gd u(n) = \frac1\ga \gd u(n-1) + \frac{\gb^n}{\ga^{n+1}} \gs u(n).  
  \end{align*}
  Since symmetry allows one to assume that $u(\check n) = 1- u(n)$, we may replace $\gs u(n)$ by $2u(n)+1$ and obtain that any $u$ satisfying
  \linenopax
  \begin{align}\label{eqn:u-harmonic-on-a,b-ladder}
    u(n+1) = u(n) + \tfrac{u(n)-u(n-1)}\ga + \tfrac2\ga\left(\tfrac\gb\ga\right)^n u(n)
     + \tfrac1\ga \left(\tfrac\gb\ga\right)^n
    
  \end{align}
  is harmonic. It remains to see that $u$ has finite energy.
  
  Our estimate for $\energy(u) < \iy$ requires the assumption that $\ga > 4\gb^2$, but numerical computations indicate that $u$ defined by \eqref{eqn:u-harmonic-on-a,b-ladder} will be both bounded and of finite energy, for any $\gb < 1 < \ga$. First, note that $u(1) = \frac1\ga$ and so an immediate induction using \eqref{eqn:u-harmonic-on-a,b-ladder} shows that $\gd u(n) = u(n+1)-u(n)>0$ for all $n \geq 1$, and so $u$ is strictly increasing. Since $\gb < 1 < \ga$, we may choose $N$ so that 
  \linenopax
  \begin{align*}
    n \geq N \implies \left(\frac\gb\ga\right)^n < \frac{\ga-1}2.
  \end{align*}
  Then $n \geq N$ implies 
  \linenopax
  \begin{align}\label{eqn:ladder(u)-subexponential}
    u(n+1) \leq 2u(n) + \frac1\ga,
  \end{align}
  by using \eqref{eqn:u-harmonic-on-a,b-ladder} and the fact that $u(n)$ is increasing and $\frac\gb\ga < 1$.
  Now use \eqref{eqn:u-harmonic-on-a,b-ladder} to write
  \linenopax
  \begin{align*}
    \gd u(n)
    &= \tfrac1\ga (\gd u)(n-1) + \left(\tfrac2\ga u(n) + \tfrac1\ga\right) \left(\tfrac\gb\ga\right)^n \notag \\
    &= \tfrac1{\ga^n} (\gd u)(0) + \sum_{k=0}^{n-1} \tfrac1{\ga^k} \left(\tfrac2\ga u(n-k) + \tfrac1\ga\right) \left(\tfrac\gb\ga\right)^{n-k} \notag \\
    &= \tfrac1{\ga^{n+1}} + \tfrac{\gb(1-\gb^n)}{\ga^{n+1}(1-\gb)} 
     + \tfrac2{\ga^{n+1}} \sum_{k=1}^{n} \gb^k u(k),
  \end{align*}
  where the second line comes by iterating the first, and the third by algebraic simplification. Applying the estimate \eqref{eqn:ladder(u)-subexponential} gives 
  \linenopax
  \begin{align*}
    2 \sum_{k=1}^{n} \gb^k u(k)
    &\leq 2^2 \sum_{k=1}^{n} \gb^k u(k-1) + \tfrac2\ga \sum_{k=1}^{n} \gb^k
        = 2^2 \sum_{k=2}^{n} \gb^k u(k-1) + 2\tfrac\gb\ga \cdot \tfrac{1-\gb^n}{1-\gb},
  \end{align*}
  and iterating gives
  \linenopax
  \begin{align}\label{eqn:ladder(du)-final-est}
    \gd u(n)
    \leq \frac1{\ga^{n+1}} \left(1 + \frac{\gb(1-\gb^n)}{1-\gb} + \frac{(2\gb)^n}\ga + 2\frac\gb\ga \sum_{k=0}^{n-1} 2^k \frac{\gb^k-\gb^n}{1-\gb}\right).
  \end{align}
  Now the energy $\energy(u) = \sum_{n=0}^\iy \ga^{n+1} \left(\gd u(n)\right)^2$ can be estimated by using \eqref{eqn:ladder(du)-final-est} as follows:
  \linenopax
  \begin{align*}
    \energy(u) 
    &\leq \sum_{n=0}^\iy \frac1{\ga^{n+1}} \left(1 + \frac{\gb(1-\gb^n)}{1-\gb} + \frac{(2\gb)^n}\ga + \frac{2\gb + 2\gb^{n+1} - 2^{n+2}\gb^{n+1} - 2^2\gb^{n+2} + (2\gb)^{n+2}}{\ga (1-\gb) (2\gb-1)}\right)^2
  \end{align*}
  and the condition $\ga > 4\gb^2$ ensures convergence.
  
  Note that this computations above can be slightly refined: instead of $\ga > 4\gb^2$, one need only assume that $\ga > (1 + \frac1\ga)^2\gb^2$. Then, fix $\ge>0$ for which $\ga / \gb^2 > (1 + \frac1\ga)^2 + \ge$ and choose $N$ so that $n \geq N$ implies $\left(\gb/\ga\right)^n < 1 + \frac1\ga + \ge(1 + 2\ga + \ga\ge)$. Then the calculations can be repeated, with most occurrences of $2$ replaced by $1+\frac1\ga+\ge$. 
\end{exm}

\begin{remark}\label{rem:comp-ladder-example-to-Z1}[Comparison of Example~\ref{exm:a,b-ladder} to the 1-dimensional integer lattice]
  Example~\ref{def:geometric-half-integers} shows that for $\ga > 1$, the ``geometric half-integers'' network
  \linenopax
  \begin{align*}
    \xymatrix{
      0 \ar@{-}[r]^{\ga} 
      & 1 \ar@{-}[r]^{\ga^2} 
      & 2 \ar@{-}[r]^{\ga^3} 
      & 3 \ar@{-}[r]^{\ga^4} 
      & \dots
    }
  \end{align*} 
  supports a monopole but not a harmonic function of finite energy. These conductances correspond to the biased random walk where, at each vertex, the walker has transition probabilities 
  \linenopax
  \begin{align*}
    p(n,m) = 
    \begin{cases}
      \frac1{1+\ga}, &m=n-1,  \\
      \frac{\ga}{1+\ga}, &m=n+1. 
    \end{cases}
  \end{align*}
  In particular, this is a spatially homogeneous distribution.
  In contrast, the random walk corresponding to Example~\ref{exm:a,b-ladder} has transition probabilities 
  \linenopax
  \begin{align*}
    p(n,m) = 
    \begin{cases}
      \frac1{1 + \ga + \left(\frac\gb\ga\right)^n}, &m=n-1,\\
      \frac{\ga}{1 + \ga + \left(\frac\gb\ga\right)^n}, &m=n+1, \vstr[2.5] \\
      \frac{\left(\gb/\ga\right)^n}{1 + \ga + \left(\frac\gb\ga\right)^n}, &m=\check n. \vstr[2.5]
    \end{cases}
  \end{align*}
  Thus, Example~\ref{exm:a,b-ladder} is geometrically asymptotic to the geometric half-integers. 
  
  \pgap
  
  One can even think of Example~\ref{exm:a,b-ladder} as describing the \emph{scattering theory} of the geometric half-integer model, in the sense of \cite{Lax-Phillips}. In this theory, a wave (described by a function) travels towards an obstacle. After the wave collides with the obstacle, the original function is transformed (via the ``scattering operator'') and the resulting wave travels away from the obstacle. The scattering is typically localized in some sense, corresponding to the location of the collision.
  
  To see the analogy with the present scenario, consider the current flow defined by the harmonic function $u$ constructed in Example~\ref{exm:a,b-ladder}, i.e., induced by Ohm's law: $\curr(x,y) = \cond_{xy}(u(x) - u(y))$. With $\act_{_{|\curr|}}(x) := \frac12\sum_{\{z \suth \curr(x,z) > 0\}} |\curr(x,z)|$, this current defines a Markov process with transition probabilities
  \linenopax
  \begin{align*}
    P(x,y) = \frac{\curr(x,y)}{\act_{_{|\curr|}}(x)},
    \q\text{if}\q \curr(x,y)>0,
  \end{align*}
  and $P(x,y) = 0$ otherwise; see \S\ref{sec:Probabilistic-interpretation} and also \cite{RANR}. This describes a random walk where a walker started on the bottom edge of the ladder will tend to step leftwards, but with a geometrically increasing probability of stepping to the upper edge, and then walking rightwards off towards infinity. The walker corresponds to the wave, which is scattered as it approaches the geometrically localized obstacle at the origin.
\end{remark}


\section{Remarks and references}
\label{sec:Remarks-and-References-examples}

The material of this chapter is an assortment of examples, some finite weighted graphs and others infinite. The infinite models are understood with the use of limit considerations. A good background reference is \cite{LevPerWil08}.
Additionally, the reader may find the sources \cite{Woess00, Woe03, KaimanovichWoess02, Kig03, Kig01, Lyo03, LPS03, LyPe03, HeLy03, HaJo02, Per09, FHS09, MiSh09} to be useful.


\version{}{
\begin{exm}[Two-sided ladder model]\label{exm:two-sided-ladder-model}
  Consider a graph which appears as a sideways ladder with $n$ rungs extending in either direction:
  \begin{equation}\label{eqn:exm:two-sided-ladder-model}
    \xymatrix{
    x_{-n} \ar[d] & \dots \ar[d] \ar[l] & x_{-1} \ar[d] \ar[l]
      &{\ga = x_0} \ar[l] \ar[r] \ar[d]
      & x_1 \ar[r] \ar[d] & \dots \ar[d] \ar[r] & x_n \ar[d] \\
    y_{-n} \ar[r] & \dots \ar[r] & y_{-1} \ar[r]
      &{\gw = y_0} & y_1 \ar[l] & \dots \ar[l] & y_n \ar[l]
    }
  \end{equation}
  We wish to find the minimizing current upon inserting one amp at the top center
  and withdrawing one amp from the bottom center.
  \version{}{\marginpar{Must add ...}}
  How does the flow respond as
  $n$ increases, and what happens as $n \to\iy$? \\

  [[To be added]]
\end{exm}
}


\version{}{
\pgap

\subsection{Vertices of infinite degree}
\label{sec:vertices-of-infinite degree}

As in \S\ref{sec:Properties-of-Lap-on-HE}, vertices of infinite degree and unbounded conductances make it possible that $\spn\{\gd_x - \gd_o\}$ is not dense in $\spn\{\gd_x\}$. 

\begin{exm}[The augmented integers]\label{exm:augmented-integers}
  Consider the integers with edges between nearest neighbours $(\bZ,\cond)$, where $\cond$
  \begin{equation}\label{eqn:exm:two-sided-ladder-model}
    \xymatrix{
    x_{-n} \ar[d] & \dots \ar[d] \ar[l] & x_{-1} \ar[d] \ar[l]
      &{\ga = x_0} \ar[l] \ar[r] \ar[d]
      & x_1 \ar[r] \ar[d] & \dots \ar[d] \ar[r] & x_n \ar[d] \\
    y_{-n} \ar[r] & \dots \ar[r] & y_{-1} \ar[r]
      &{\gw = y_0} & y_1 \ar[l] & \dots \ar[l] & y_n \ar[l]
    }
  \end{equation}
\end{exm}


\pgap
}
{"config": "arxiv", "file": "0806.3881/examples.tex"}