
% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.20}{21(4)}{2014}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{amsthm}
\usepackage{latexsym,bezier,gastex,amsbsy,enumerate,amsfonts,amsmath,amscd,amssymb}%,setspace}
%\usepackage{simplemargins}
%\usepackage[latin1]{inputenc}
%\usepackage{graphics}
%\usepackage{epsfig}
%\documentclass[smallextended]{svjour3}
%\documentclass[smallextended]{svjour3}
\usepackage{autograph2,epic,latexsym,graphics,color,bezier,amsbsy,enumerate,amsfonts,amsmath,amscd,amssymb}




\newtheorem{defi}{Definition}[section]
\newtheorem{teo}[defi]{Theorem}
\newtheorem{lem}[defi]{Lemma}
\newtheorem{prop}[defi]{Proposition}
\newtheorem{cor}[defi]{Corollary}
\newtheorem{oss}[defi]{Remarks}
\newtheorem{es}[defi]{Example}
\newtheorem{ess}[defi]{Examples}
\newtheorem{prova}{Proof.}
\newtheorem{os}[defi]{Remark}
%\renewcommand{\subjclassname}{2000 Mathematics Subject Classification}


\begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{\bf Schreier graphs of an extended version \\ of the binary adding machine}
\author{ Daniele D'Angeli\thanks{The author was supported by Austrian Science Fund project FWF P24028-N18.}  \\
\small{Institut f\"{u}r Mathematische Strukturtheorie (Math C)}\\[-0.8ex]
\small{Technische Universit\"{a}t Graz, Austria}\\
%Tel. +43 (316) 873 - 7631\\
\small{\tt dangeli@math.tugraz.at}}


\date{\dateline{Jul 23, 2013}{Oct 18, 2014}{Oct 30, 2014}\\
\small Mathematics Subject Classifications: 20E08, 20F69, 37E25 }

\unitlength=0,4mm










\maketitle





\begin{abstract}
In this paper we give a complete classification of
the infinite Schreier graphs of an automaton group generated by an extended version of the binary adding machine.\\
\\
\noindent \textbf{Keywords:} Schreier graphs, ends, automata groups, bounded
automaton.
\end{abstract}



%\begin{center}
%{\footnotesize{\bf Mathematics Subject Classification (2010)}:
%20E08, 20F69, 37E25.}
%\end{center}

\section{Introduction}


The motivation for this article is the paper \cite{nonamenable}
where R. Grigorchuk and V. Nekrashevych provide
amenable actions of nonamenable groups by extending the
action of a nonamenable group acting by automorphisms on a
rooted tree (for example the Bellaterra group) to a larger tree in a suitable way.
In this paper we consider a similar construction: we take the
adding machine, isomorphic to $\mathbb{Z}$, which is the simplest finitely generated
automaton group acting transitively on each level of the rooted binary
tree. If $a$ is the generator of the
binary adding machine we extend its action on a ternary tree in
such a way that whenever $a$ reads the new symbol ``2" then its
action becomes trivial on the remaining word. In order to have transitivity we also add a new automorphism which generates the adding machine acting on the rooted ternary tree. The group $G$
obtained by this construction is generated by the
automorphisms $a=(id,a,id)(01)$ and $b=(id,id,b)(012)$. In our case, since the binary adding machine is
generated by a bounded automaton then $G$ is also generated by a
bounded automaton \cite{sidki}, in particular $G$ is amenable \cite{amenability bounded}. This way it is possible to define a new class of groups that
can be regarded as extended versions of groups acting on a smaller
tree and investigate the structure of the corresponding Schreier graphs, that represent the action on any level of the rooted tree, or can be defined through the vertex stabilizers.
Passing to the boundary, $G$ gives rise to uncountably many infinite Schreier graphs: the problem is to classify them.
In this paper we give a complete (topological and isometric) classification of the infinite
Schreier graphs of $G$, showing, in particular, that they are typically one ended (Theorem~\ref{ends}) and there are infinitely many isomorphism classes, each containing either one or two orbital graphs (Theorem~\ref{teoclass}). We think that most of the
strategies used for the Schreier graphs of $G$ can be exploited, at least for the topological classification, to study
more sophisticated examples of such a construction, i.e. replacing the binary adding machine by another more complicated group (see, for instance Remark~\ref{remarkfinale}). On the other hand, the isomorphism problem can be directly treated in the case here discussed, because of the special structure of the two kinds of Schreier graphs involved in the construction. For more general examples the problem looks much more difficult. By the way it would be even interesting to apply our construction to examples of groups generated by non-bounded automata, such as Aleshyn free automaton or Bellaterra automaton. In this context one might discuss some questions related to Schreier graphs such as the existence of orbital graphs with different growth rate, the possibility of getting graphs of polynomial growth through the action of groups containing free subgroups, the construction of totally non-free boundary actions for groups which are not weakly regular branch \cite{bonda, dynamicssubgroup, savchuk}.

It is worth mentioning here that the notion of Schreier graph is classical in group theory, and it corresponds to the action of a finitely generated group $\mathfrak{G}$ on the set of cosets $\mathfrak{G}/\mathfrak{H}$ with respect to a subgroup $\mathfrak{H}$. In our context $\mathfrak{H}$ represents the stabilizer of a vertex of the tree (finite Schreier graphs) or a vertex of the boundary of the (infinite Schreier graphs). From this description it is clear that, if a boundary point admits a trivial stabilizer the corresponding Schreier graph coincides with the Cayley graph of the group. In our case we can prove that no infinite Schreier graph equals the Cayley graph of $G$ and moreover almost all stabilizers of boundary points are different. Connections between the structure of the Schreier graphs and properties of the generating group can be found in \cite{emanuele2}, where among other results the authors provide finiteness results in terms of boundary Schreier graphs by using the dual approach. In \cite{nekra} V. Nekrashevych shows that if a group
acting faithfully on a rooted tree has a free subgroup, then either there exists a point $x$ of the boundary
and a free subgroup with trivial stabilizer (and so the Schreier graph of $x$ contains a subtree), or there exists a free subgroup fixing $x$ and acting faithfully on arbitrarily small
neighborhoods of $x$.

Our paper follows the results obtained for the
Basilica group \cite{basilica}, for groups generated
by bounded automata \cite{BDN} and for a group generated by a linear automaton \cite{cucu}.
The study of Schreier graphs of
some examples of automata groups was initiated by L.
Bartholdi and R. Grigorchuk \cite{hecketype} in connection with
the problem of determining the spectrum of the associated Laplace
operator. Particularly interesting examples come from the class of
self-similar groups, which are connected to self-similar sets via
the notion of limit space, which is a compact space that can be
associated with any contracting self-similar group
\cite{nekrashevyc}. A new interesting
study of Schreier graphs appears in connection with colorings and subgroup
dynamics \cite{emanuele, dynamicssubgroup, vorobets}.

%\begin{figure}
%\includegraphics[scale=0.4]{prova} \caption{gioppino}
%\end{figure}

\section{Preliminaries: Automata groups}

Let $X = \{0,1, \ldots, q-1\}$ denote
an alphabet of $q$ elements. We denote by $X^n$ the set of words of length $n$ in $X$ and $X^{\ast}=\cup_n X^n$. The set of right (resp. left) infinite words is denoted by $X^{\omega}$ (resp. $X^{-\omega}$). The set $X^{\ast}$ encodes the vertices of a rooted tree
in a natural way and $X^{\omega}$ the relative boundary.
An automorphism of $X^{\ast}$ is a bijection preserving the adjacency relation in the corresponding tree.
The action of an automorphism $g$ on a vertex $v\in X^{\ast}$ is
denoted by $g(v)$. The orbit of $v$ under $g$ is $g\cdot v:=\{g^n(v): \ n\in \mathbb{Z}\}$.

An \textit{automaton} is a quadruple $\mathcal{A} =
(\mathcal{S},X,\mu,\lambda)$, where:
 $\mathcal{S}$ is a set, called set of states, $X$ is an alphabet as before,
 $\mu: \mathcal{S}\times X \rightarrow \mathcal{S}$ is the transition map and
$\lambda: \mathcal{S}\times X \rightarrow X$ is the output map. The automaton $\mathcal{A}$ is said to be \textit{finite} if
$\mathcal{S}$ is finite and it is said \textit{invertible} if, for
all $s\in \mathcal{S}$, the transformation $\lambda(s,
\cdot):X\rightarrow X$ is a permutation of $X$. An automaton
$\mathcal{A}$ can be represented by its \textit{Moore diagram}:
a directed labelled graph whose vertices are identified
with the states of $\mathcal{A}$. For every state $s\in
\mathcal{S} $ and every letter $x\in X$, the diagram has an arrow
from $s$ to $\mu(s,x)$ labelled by $x|\lambda(s,x)$. A natural
action on the words over $X$ is induced, so that the maps $\mu$
and $\lambda$ can be extended to $\mathcal{S}\times X^{\ast}$ as:
\begin{eqnarray}
\mu(s,xw) = \mu(\mu(s,x),w)
\end{eqnarray}
\begin{eqnarray}\label{actionextended}
\lambda(s,xw) = \lambda(s,x)\lambda(\mu(s,x),w),
\end{eqnarray}
by setting $\mu(s,\emptyset) = s$ and $\lambda(s,\emptyset) =
\emptyset$, for all $s\in \mathcal{S}, x\in X$ and $w\in
X^{\ast}$. Moreover, (\ref{actionextended}) uniquely defines a map
$\lambda: \mathcal{S} \times X^{\omega}\rightarrow X^{\omega}$.

Fixed an initial state $s$ in $\mathcal{A}$,
the transformation $\mathcal{A}_s$ on the set $X^{\ast}\cup
X^{\omega}$ is induced by the recursion (\ref{actionextended}). More generally,
given an invertible automaton $\mathcal{A} =
(\mathcal{S},X,\mu,\lambda)$, one can consider the group generated
by the transformations $\mathcal{A}_s$, for $s\in \mathcal{S}$:
this group is called the \textit{automaton group} generated by
$\mathcal{A}$ and is denoted by $G(\mathcal{A})$. A state $s$ in $\mathcal{A}$ with the property that $\mu(s,w)=s$ and $\lambda(s,w)=w$, for all $w\in X^{\ast}$ is said to be trivial and it is usually denoted by $id$. Clearly $\mathcal{A}_{id}$ represents in this case, the identity element in $G(\mathcal{A})$. The post-critical (resp. critical) set $\mathcal{P}$ of the automaton $\mathcal{A}$ is the set of
left(resp. right)-infinite words $\ldots x_2x_1\in X^{-\omega}$ (resp. $x_1x_2\ldots\in X^{\omega}$) such that there
exists a path $\ldots e_2e_1$  (resp. $e_1e_2\ldots$) in the Moore diagram of
$\mathcal{A}$, ending in a non-trivial state (resp. avoiding the trivial state) such that the word
$\ldots x_2x_1$ (resp. $x_1x_2\ldots$) can be read on the left (resp. the right) labels of
the path $\ldots e_2e_1$ (resp. $e_1e_2\ldots$). A finite invertible automaton is \textit{bounded} if $|\mathcal{P}|<\infty$.

Groups generated by automata are also known as \textit{self-similar groups} \cite{nekrashevyc}, when one wants to emphasize the action on the rooted tree. We can represent any element $s\in \mathcal{S}$ in its self-similar form $s=(s_0,s_1,\ldots, s_{q-1})\sigma$ where $s_i=\mu(s,i)$ and $\sigma$ is the permutation induced by $s$ and $\lambda$ on $X$. This representation extends to all elements of $G=G(\mathcal{A})$ after embedding into
the wreath product $G\wr_X S_q= (G^q) \rtimes S_q$, where $S_q$ is the
symmetric group on $q$ elements.

\section{Constructions}

The adding machine $\mathcal{G}$ is the automaton group isomorphic to $\mathbb{Z}$ generated by the automaton in the left side of Figure 1 or, equivalently by $a=(id,a)(01)$. This group acts on the binary tree and
it is, in some sense, the simplest example of a self-similar
spherically transitive infinite group. Let us introduce a new symbol ``2'', so that the new alphabet
is $X=\{0,1,2\}$. We denote by $b$ the new automorphism
guaranteeing the transitivity: it acts as the adding machine
$b=(id,id,b)(012)$ on the ternary tree.
%\begin{figure}
%\includegraphics[scale=0.6]{alberi}
%\caption{The action of $a$ and $b$ on the ternary tree}
%\end{figure}
The automorphism $a$ keeps its action on the set $\{0,1\}^{\omega}$ and is such that $\lambda(a,2)=2$ and $\mu(a,2)=id$. In
self-similar form we get $a=(id, a , id)(01)$. Consider the automorphisms $a=(id, a , id)(01)$ and
$b=(id,id,b)(012)$. Let $G$ be the automaton group generated by $a$ and $b$, see the right picture in Figure 1.

%\begin{figure}
%\includegraphics[scale=0.2]{addingdani}
%includegraphics[scale=0.2]{adding2dani}
%\caption{The binary adding machine and automaton generating $G$}
%\end{figure}

\begin{center}
\begin{picture}(300,100)
\thicklines \setvertexdiam{20} \setprofcurve{0}\setloopdiam{20}
\letstate A=(200,70)
\letstate B=(130,30)
\letstate C=(270,30)

\drawstate(A){$b$} \drawstate(B){$id$} \drawstate(C){$a$} \small{
\drawcurvededge(A,B){$0|1$, $1|2$}\drawcurvededge(C,B){$0|1$,$2|2$}
\setprofcurve{0} \drawloop[r](C){$1|0$} \drawloop[r](A){$2|0$}\drawloop[l](B){$0|0,1|1,2|2$}
}


\thicklines \setvertexdiam{20} \setprofcurve{15}\setloopdiam{20}
\letstate F=(25,80)
\letstate G=(95,80)

\drawstate(F){$a$} \drawstate(G){$id$} \small{
\drawedge(F,G){$0|1$}
\setprofcurve{-20}
\drawloop[r](G){$0|0,1|1$} \drawloop[l](F){$1|0$}}
\put(24,5){\textbf{Figure} 1. The automata generating the Adding machine and $G$}
\end{picture}
\end{center}


\subsection{Schreier graphs: definitions}\label{def} 

In this section we introduce some
basic facts about Schreier graphs.
Let $G$ be a finitely generated group generated by a finite set
$S$ and suppose that $id \not \in S$ and $S = S^{-1}$. Let $G$ act
faithfully on a set $M$. The \textit{Schreier graph} $\Gamma=\Gamma(G,S,M)$ is the
graph with vertices and edges given by $V(\Gamma)=M$ and $E(\Gamma)=\{(m,m') : \textrm{ there exists $s\in S$ such that $s(m)=m'$}\}$. In this case the edge $(m,m')$ is labeled by $s$. In our classification we remove any label from the edges.

In our setting the group $G$ acts on the set $X^n$, since $G$ is transitive the corresponding Schreier graph $\Gamma_n=\Gamma(G,S,X^n)$ is connected, and it represents the orbital graph of (any) point $v$ in $X^n$ under the action of the generators.

Consider now the action of $G$ on $X^{\omega}$ and the
orbital Schreier graphs $\Gamma_{\xi}=\Gamma(G,S,G\cdot\xi)$, for
$\xi=\xi_1\xi_2\ldots\in X^{\omega}$. Put $\underline{\xi}_n =
\xi_1\xi_2\ldots \xi_n$. We recall that a marked graph
$(\Gamma,v)$ is a graph in which a vertex $v$ is distinguished. It
turns out that the graphs $(\Gamma_{\xi},\xi)$ are limits of
the Schreier graphs $(\Gamma_n,\underline{\xi}_n)$ in the
sense of the topology induced by the metric $Dist$ on the space of
marked graphs defined as follows \cite{grizukprimo}:
\begin{displaymath}
Dist((\Gamma_1,v_1),(\Gamma_2,v_2)):=\inf\left\{\frac{1}{n+1};\textrm{$B_{\Gamma_1}(v_1,n)\simeq
B_{\Gamma_2}(v_2,n)$}\right\}
\end{displaymath}
\noindent where $B_{\Gamma}(v,n)$ is the ball of radius $n$ in
$\Gamma$ centered at $v$ \cite{ihara}

\begin{os}\label{remarkdistanze} \rm
One can show that if there exists $K>0$ such that the distance in
$\Gamma_n$ between $\underline{\xi}_n$ and
$\underline{\eta}_n$ is smaller than $K$ for each $n\in
\mathbb{N}$, then $\Gamma_{\xi}=\Gamma_{\eta}$ (as non-marked graphs) \cite{basilica}.
\end{os}

\subsection{Schreier graphs of $G$}\label{schreier} 

The Schreier graphs of the
adding machine $\mathcal{G}$ are easily described. These can be
represented by ``polygons'' (we will use this word) of prescribed length. One can identify
$\{0,1,\ldots, q-1\}^n$ with
the elements of the abelian group $\mathbb{Z}/q^n\mathbb{Z}$. The vertex
$x_1x_2\cdots x_n$, $x_i\in \{0,1,\ldots, q-1\}$ corresponds to the element $\sum_{i=1}^n
x_iq^{i-1}$ (mod $q^n$). The generating element of the adding
machine $\mathcal{G}$ acts on a vertex by adding $+1$ to the
corresponding element in the group. In our case we are combining
two graphs of this type: the $n-$th Schreier graphs $\Upsilon_n$ of the
group generated by $a=(id,a)(01)$ and $\Sigma_n$ of the group
generated by $b=(id,id,b)(012)$. As we remarked $\Upsilon_n$ is a
polygon of length $2^n$ and $\Sigma_n$ a polygon of length $3^n$.

Denote by $\Gamma_n$ the $n-$th Schreier graph of the group $G$.
Let $\underline{x}_m$ represent a word of length $m$ in the
alphabet $X$ and introduce the partition given by the sets
\begin{eqnarray*}
X_k^n(\underline{x}_{n-k-1})&=&\{ x_1\cdots x_{k}2x_{k+2}\cdots
x_n :  \ x_i\in \{0,1\} \\
&& \forall i=1,\ldots,k, \ \underline{x}_{n-k-1}=x_{k+2}\cdots x_n
\},
\end{eqnarray*}
for any $k=1,\ldots, n-1$. Fixed $k$ we have $3^{n-k-1}$ disjoint copies of such
subsets. Moreover define
$$
X_n^n:=X_n^n(\emptyset)=\{ x_1\cdots x_n : \ x_i\in
\{0,1\} \ \forall i=1,\ldots,n \}.
$$
Each of the sets $X_k^n(\underline{x}_{n-k-1})$, for $k=1,\ldots,n-1$ and $X_n^n$ is invariant under the action of the subgroup
$\langle a\rangle$ of $G$. Moreover the action of $\langle
a\rangle$ on $X_k^n(\underline{x}_{n-k-1})$ and on $X_n^n$ is
clearly transitive. In $\Gamma_n$ the set
$X_k^n(\underline{x}_{n-k-1})$ together with the edges given by the $a$-action, is a copy of the Schreier graph
$\Upsilon_{k}$, so that in $\Gamma_n$ we have $3^{n-1}$ loops
corresponding to the words starting by $2$, $3^{n-k-1}$ copies of
$\Upsilon_{k}$, for any $k=1,\ldots, n-1$ and one copy of
$\Upsilon_n$.

A suitable way for describing the structure of the graph $\Gamma_n$ is the following:
an ``external'' polygon of size $3^n$ isomorphic to $\Sigma_n$ and
labeled by $b$ (containing all vertices and corresponding to the
action of the generator $b$). Inside this polygon other polygons isomorphic to the $\Upsilon_k$'s
(in number established above) corresponding to the action of $a$.
In Figure 2 there are the first two Schreier graphs of $G$.

%\begin{figure}
%\begin{center}
%\includegraphics[scale=0.4]{Schreier12}
%\caption{The Schreier graphs $\Gamma_1$ and $\Gamma_2$ of $G$}
%\end{center}
%\end{figure}



From this we get the following result.

\begin{prop}
For every $n$, the graph $\Gamma_n$ is planar.
\end{prop}

\begin{proof} Suppose, by contradiction, that there are four vertices $u_i\in \Gamma_n$, $i=1,2,3,4$, and positive numbers $t_i$ such that $b^{t_i}(u_i)=u_{i+1}$, for $i=1,2,3$, $a(u_i)=u_{i+1}$, for $i=1,2$. We can assume $u_1,u_3\in X_k^n(\underline{x}_{n-k-1})$ and $u_2,u_4 \in X_h^n(\underline{x'}_{n-h-1})$, for some $k,h, \underline{x}_{n-k-1}, \underline{x'}_{n-h-1}$ in such a way that $X_k^n(\underline{x}_{n-k-1})\neq X_h^n(\underline{x'}_{n-h-1})$. By the assumption we have that $u_1=u_1'2p$, $u_3=u_3'2p$, $u_2=u_2'2q$ and $u_4=u_4'2q$, for some subwords $u_i', p, q, p\neq q$ and we can suppose, without loss of generality, that $|p|\leq |q|$. This implies that, for every $i=1,\ldots, t_1+t_2$ one has $b^i|_{u_1'2}= id$ and this is in contradiction with the fact that $p\neq q$.
\end{proof}

\begin{center}
\begin{picture}(400,120)
 \setprofcurve{11}

\letvertex A=(80,50)\letvertex B=(100,100)\letvertex C=(120,50)
\drawvertex(A){$\bullet$}\drawvertex(B){$\bullet$}
\drawvertex(C){$\bullet$}
\drawundirectededge(A,B){$b$}\drawundirectededge(C,A){$b$}
\drawundirectededge(C,B){$a$}\drawundirectedcurvededge(B,C){$b$}
\drawundirectedloop[l](A){$a$}
\put(80,40){$2$}\put(120,40){$1$}\put(97,103){$0$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\letvertex E=(270,120)\letvertex F=(310,100)\letvertex G=(318,75)\letvertex H=(310,50)\letvertex I=(270,20)\letvertex L=(230,20)\letvertex M=(200,50)\letvertex N=(200,100)\letvertex O=(230,120)
\drawvertex(N){$\bullet$}\drawvertex(O){$\bullet$}
\drawvertex(M){$\bullet$}\drawvertex(E){$\bullet$}\drawvertex(F){$\bullet$}
\drawvertex(I){$\bullet$}\drawvertex(H){$\bullet$}\drawvertex(G){$\bullet$}
\drawvertex(L){$\bullet$}

\put(265,124){$00$}\put(310,102){$10$}\put(326,82){$20$}\put(310,40){$01$}\put(275,10){$11$}\put(227,10){$21$}\put(187,47){$02$}\put(187,102){$12$}\put(227,124){$22$}


\drawundirectededge(E,F){$b$}\drawundirectededge(F,G){$b$}\drawundirectededge(G,H){$b$}\drawundirectededge(H,I){$b$}\drawundirectededge(I,L){$b$}
\drawundirectededge(L,M){$b$}\drawundirectededge(M,N){$b$}\drawundirectededge(N,O){$b$}\drawundirectededge(O,E){$b$}

\drawundirectedloop[r](G){$a$}\drawundirectedloop[l](O){$a$}\drawundirectedloop[l](L){$a$}

\drawundirectededge(I,E){$a$}\drawundirectedcurvededge(I,H){$a$}\drawundirectedcurvededge(H,F){$a$}
\drawundirectedcurvededge(F,E){$a$}\drawundirectedcurvededge(N,M){$a$}

\small{
\put(100,-2){\textbf{Figure} 2. The Schreier graphs $\Gamma_1$ and $\Gamma_2$ of $G$}}
\end{picture}
\end{center}

\subsection{Orderings in $\Gamma_n$} \label{orderings} 

Any vertex $x=x_1\cdots x_n$ in $\Gamma_n$ represents the number (that we improperly denote by)
$x=\sum_{i=1}^n 3^{i-1}x_i$, so that there exists a natural order in
$\Gamma_n$, coherent with the action of $b$. Given
$x,v,w\in \Gamma_n$, we write $x\in [v,w]$ if $v\leq x\leq w$, so
that for any $x$ we have $x\in [0^n,2^n]$.
\begin{os}\rm\label{verticisimmetrici}
For every $n$, consider the sets of pairs $\{(\alpha_k,\beta_k): \ \alpha_k=b^k(0^n),\beta_k= b^{-k}(1^n))$,$ \ k=0,1,\ldots, \frac{3^n+1}{2}\}$ and $\{(\varsigma_k,\theta_k): \ \varsigma_k=b^k(1^n), \theta_k= b^{-k}(2^n)), \ k=1,\ldots, \frac{3^n+1}{2}\}$. It follows by induction that only for such couples one has $\alpha_k+\beta_k=\sum_{i=0}^{n-1}3^i$ (for $k=0,1,\ldots, \frac{3^n+1}{2}$) and $\theta_k+\varsigma_k=\sum_{i=0}^{n}3^i$ (for $k=1,\ldots, \frac{3^n+1}{2}$), where the sum of the strings is considered in base $3$.
\end{os}

\begin{defi}
Let $v$ be a vertex in $ \Gamma_n$, we say that $v$ is
\textit{under} $\Upsilon_n$ (we write $v\uparrow \Upsilon_n$) if $v\in
[0^n,1^n]$ and $v\not\in X^n_n$.
\end{defi}

\begin{os}\label{remarkunder}\rm
It is clear that if $v\not\in X_n^n$ and $v_n=0$ then $v\uparrow
\Upsilon_n$. Moreover if $v\not\in X_n^n$, $v_n=1$ and $v_k=0$, with $k$
the largest index such that $v_{k}\neq 1$, $v_{k+1}=1$, then
$v\uparrow \Upsilon_n$.
\end{os}

Now we can describe what is the position (in the graph
$\Gamma_{n+1}$) of a vertex $v\in \Gamma_n$, after adding the final letter $0,1,2$.
We distinguish the following cases.
\begin{itemize}
  \item If $v\in X_n^n$, then $v0, v1\in X_{n+1}^{n+1}$ and $v2\in [0^n2,1^n2]$.
  \item If $v\not\in X_n^n$ and $v\uparrow \Upsilon_n$, then $v0,v1 \uparrow
  \Upsilon_{n+1}$ and $v2\in [0^n2,1^n2]$.
  \item If $v\not\in X_n^n$ and $v$ is not under $\Upsilon_n$, then $v0\uparrow
  \Upsilon_{n+1}$, and $v1,v2$ are not under $\Upsilon_n$ and $\Upsilon_{n+1}$, and $v1 \in
  [1^{n+1},0^n2]$, $v2\in [1^n2,2^{n+1}]$.
\end{itemize}

\subsection{Infinite Schreier graphs of $G$: the number of ends} \label{infin} 

In this section we describe the infinite Schreier graphs associated with the
group $G$. We already defined in Section \ref{def} the infinite
Schreier graphs of the action of the group $G$ on the
boundary of the tree.

$G$ is generated by a bounded automaton, it is easy to check that
the post-critical set consists of three elements
$\mathcal{P}=\{0^{-\omega}, 1^{-\omega}, 2^{-\omega}\}$. For the
group $G$ we will provide a topological classification of the
infinite Schreier graphs (in terms of ends) and a classification
up to isomorphism.

We recall that two (right) infinite words $\xi=\xi_1\xi_2\cdots$
and $\eta=\eta_1\eta_2\cdots$ are \textit{cofinal} (an we shall write $\xi\sim \eta
$) if there exists $n\in \mathbb{N}$ such that $\xi_k=\eta_k$ for
all $k\geq n$. Given $\xi \in X^{\omega}$, as before
$\underline{\xi}_n$ denotes the prefix $\xi_1\cdots\xi_n$ of length $n$ of
$\xi$. The set of all words cofinal to $\xi$ is denoted by
$Cof(\xi)$.

It is easy to prove that if $\xi\sim\eta$ then the corresponding
infinite Schreier graphs are isomorphic (as non-marked graphs)
$\Gamma_{\xi}\simeq \Gamma_{\eta}$. In fact $\xi\sim\eta$ implies
that the elements $\xi$ and $\eta$ belong to the same orbital
graph (see \cite{basilica}). More precisely if $\xi$ is not critical the vertex set of $\Gamma_{\xi}$ coincides with $Cof(\xi)$. In our case the vertex set of $\Gamma_{0^{\omega}}$ ($=\Gamma_{1^{\omega}},\Gamma_{2^{\omega}}$) is given by $Cof(0^{\omega})\sqcup Cof(1^{\omega})\sqcup Cof(2^{\omega})$.

Let $\Gamma= (V,E)$ be an infinite graph, a ray is an infinite
sequence of distinct vertices such that any two consecutive
vertices of this sequence are adjacent in $\Gamma$. Consider an
equivalence relation on the set of rays: two rays $R$ and $R'$ are
equivalent if for any finite set $S \subseteq V$ both $R$ and $R'$
have a tail in the same component of $\Gamma\setminus S$. An \textit{end} is an equivalence class of
rays. Note that every infinite, locally finite graph must have at
least one end.

In what follows we generalize some notions introduced before to the case of infinite Schreier graphs. Given $\xi, v,w \in X^{\omega}$, we write $v<w$ if there exist $k>0$ such that
$b^k(v)=w$ and we write
$\xi\in [v,w]$ if there exist $k,h\in \mathbb{N}$ such that
$b^h(v)=\xi$ and $b^k(\xi)=w$. Moreover $\xi \uparrow \Upsilon_n$ if $\xi\in [0^n2\xi_{n+2}\cdots,1^n2\xi_{n+2}\cdots]$.

Let $E_i$ be the set of right-infinite words whose infinite
Schreier graph is $i-$ended. More precisely
$$
E_i=\{\xi \in X^{\omega} : \ \Gamma_{\xi} \ \textrm{is} \
i\textrm{-ended}\}
$$

The uniform measure on the boundary, generated by the cones
$wX^{\omega}$ of the tree is denoted by $m$.

\begin{teo}\label{ends}
Let $G$ be the group defined above, then:
\begin{itemize}
  \item $E_4=Cof(0^{\omega})\sqcup Cof(1^{\omega})\sqcup
  Cof(2^{\omega})$, and consists of one orbit, so that $m(E_4)=0$.
  \item $E_2= (A(2)\sqcup A(0))\setminus E_4 $ consists of uncountably many orbits where
  $$
  A(2)=\{\xi \in X^{\omega} : \ \xi\sim \vartheta, \ \vartheta_i\neq 2 \ \forall i
  \},
  $$
  $$
  A(0)=\{\xi \in X^{\omega} : \ \xi\sim \theta, \ \theta_i\neq 0 \ \forall i
  \}.
  $$
  Moreover $m(E_2)=0$.
  \item $E_1= X^{\omega}\setminus (E_4 \sqcup E_2)$ consists of uncountably many orbits and
  $m(E_1)=1$.
\end{itemize}
\end{teo}

\begin{proof} The vertices $0^{\omega},1^{\omega},2^{\omega}$
are in the same orbit since $b(2^{\omega})=0^{\omega}$ and
$a(1^{\omega})=0^{\omega}$. These three elements give rise to the
only non-cofinal words which belong to the same graph. The
$b-$orbit of $2^{\omega}$ contains $Cof(0^{\omega})$ and
$Cof(2^{\omega})$. The $a-$action on $1^{\omega}$ contains
$Cof(0^{\omega})$ and $Cof(1^{\omega})$. The generator $b$ sends
vertices in $Cof(2^{\omega})\setminus 2^{\omega}\sqcup
Cof(1^{\omega})\sqcup Cof(0^{\omega})$ to vertices in
$Cof(2^{\omega})\setminus 2^{\omega}\sqcup Cof(1^{\omega})\sqcup
Cof(0^{\omega})$. On the other hand $a$ sends vertices in
$Cof(1^{\omega})\setminus 1^{\omega}\sqcup Cof(2^{\omega})\sqcup
Cof(0^{\omega})$ to vertices in $Cof(1^{\omega})\setminus
1^{\omega}\sqcup Cof(2^{\omega})\sqcup Cof(0^{\omega})$. If we
consider $Cof(0^{\omega})\sqcup Cof(2^{\omega})$, it consists of
one line isomorphic to the Cayley graph of $\mathbb{Z}$ with generators $\pm 1$ (the $b-$orbit) with some
extra edges (the $a-$orbit) which do not join vertices of type $\{b^k(2^{\omega})\}$ to vertices in $\{b^{-k}(0^{\omega})\}$ (for $k>0$), since these are not cofinal.
This gives two ends. The vertex $0^{\omega}$ is connected to
$1^{\omega}$. The $b-$orbit on $1^{\omega}$ is another copy of the Cayley graph of $\mathbb{Z}$ disjoint from the $b-$orbit on $2^{\omega}$. For any
$k>0$ the elements in $\{b^k(1^{\omega})\}$ are not joined to the
elements in $\{b^{-k}(1^{\omega})\}$ by $a$, since all elements in $\{b^k(1^{\omega})\}$ are of type $w21^{\omega}$, for some $w$ and $\{b^{-k}(1^{\omega})\}$ contains elements of type $v201^{\omega}$, with $|v|=|w|$. So that we get two
ends, and the graph $\Gamma_{0^{\omega}}$ is 4-ended.

Let $\xi$ be an element in $A(2)$. We can suppose that $\xi_n\in
\{0,1\}$ for all $n$ and $\xi \nsim 0^{\omega}, 1^{\omega}$. The $a-$orbit $a\cdot\xi$ is a subset of $b\cdot
\xi$, since it corresponds to the elements of $b\cdot \xi$ which
do not contain 2. Moreover $a\cdot\xi$ consists
of infinite elements (this is the only infinite $a-$orbit in the graph) and since the order induced by $a$ is coherent with the order given
by $b$ (i.e. $v<w$ implies $a(v)<a(w)$) and the vertex set of $\Gamma_{\xi}$ is $Cof(\xi)$, we have that the graph
$\Gamma_{\xi}$ is 2-ended.

Let $\xi$ be an element in $A(0)$. We can suppose that for every $n$,
$\xi_n\in \{1,2\}$ and $\xi \nsim 1^{\omega}, 2^{\omega}$. From Section \ref{infin} we know that $\xi$ is
not under a polygon $\Upsilon_n$. For any $n$ we have that
$\underline{\xi}_n \in [1^n, 0^{n-1}2]\sqcup [1^{n-1}2, 2^n]$,
with the distances $d(\underline{\xi}_n, 1^n)$ and
$d(\underline{\xi}_n, 2^n)$ growing with $n$ from Remark
\ref{remarkdistanze}. Observe that $a(1^n)=b(2^n)=0^n$. For $n$
large we have $\xi\in [1^n\xi_{n+1}\cdots, 2^n\xi_{n+1}\cdots]$,
with $\xi_{n+1}\in \{1,2\} $. We have
$b(2^n\xi_{n+1}\cdots)=0^nb(\xi_{n+1}\cdots)$, so that
$a(1^n\xi_{n+1}\cdots)\neq 0^nb(\xi_{n+1}\cdots)$. Hence there is
no edge connecting two non equivalent rays in $\Gamma_{\xi}$. Clearly $m(A(0))=m(A(2))=0$ and so $m(E_2)=0$. Moreover both $A(0)$ and $A(2)$ are uncountable sets.

If $\xi\in E_1$, then $\xi$ contains infinitely many 0 and 2. This
implies $\xi \uparrow \Upsilon_n$ for infinitely many $n$. The $b-$orbit
$b\cdot \xi$ of $\xi$ consists of a copy of the Cayley graph of $\mathbb{Z}$ and
$a\cdot \xi $ is a subset of $b\cdot \xi$. Two non-equivalent rays
in $b\cdot \xi$ contain infinitely many vertices of type
$0^n\xi_{n+1}\cdots$ and $1^n\xi_{n+1}\cdots$ respectively, since
$\xi\in [0^n\xi_{n+1}\cdots, 1^n\xi_{n+1}\cdots]$. We can suppose
that $\xi_{n+1}=2$ for infinitely many indices. The rays are joint
by the $a-$edges of type $(0^n\xi_{n+1}\cdots,
1^n\xi_{n+1}\cdots)$. Moreover $m(E_1)=m(X^{\omega})=1$ and $E_1$ is clearly an uncountable set.
\end{proof}

Figure 3 shows the shape of the (unique) orbit which is a 4-ended
graph, Figure 4 an example of a 2-ended infinite Schreier graph,
Figure 5 an example of a 1-ended infinite Schreier graph.

\begin{os}\rm
The previous result agrees with the results obtained in \cite{BDN}, where the authors show that if $G$ is a
group generated by a bounded automaton whose post-critical set
contains more than 2 elements then $m(E_1)=1$.
\end{os}

\subsection{Isomorphisms} Now we pass to the problem of describing the
isomorphism classes of the infinite Schreier graphs of $G$. As we
said in Section \ref{def} the limit of infinite Schreier graphs is
defined in the space of marked graphs. If we forget the special
vertex, we can compare the structure of infinite graphs and
establish if they are isomorphic.

%\begin{figure}
%\includegraphics[scale=0.4]{4ends}
%\caption{The 4-ended infinite Schreier graphs of $G$}
%\end{figure}

\begin{picture}(400,90)
%\begin{center}

 \setprofcurve{13}

\letvertex A=(30,70)\letvertex B=(70,70)\letvertex C=(110,70)\letvertex D=(150,70)\letvertex E=(190,70)\letvertex F=(230,70)\letvertex G=(270,70)\letvertex H=(310,70)
\put(10,67){$b$}\put(10,47){$b$}\put(268,90){$a$}\put(268,30){$a$}

\letvertex I=(30,50)\letvertex L=(70,50)\letvertex M=(110,50)\letvertex N=(150,50)\letvertex O=(190,50)
\letvertex P=(230,50)\letvertex Q=(270,50)\letvertex R=(310,50)

\drawvertex(A){$\bullet$}\drawvertex(B){$\bullet$}
\drawvertex(C){$\bullet$}\drawvertex(D){$\bullet$}\drawvertex(E){$\bullet$}
\drawvertex(F){$\bullet$}\drawvertex(G){$\bullet$}\drawvertex(H){$\bullet$}
\drawvertex(I){$\bullet$}\drawvertex(L){$\bullet$}\drawvertex(M){$\bullet$}
\drawvertex(N){$\bullet$}\drawvertex(O){$\bullet$}\drawvertex(P){$\bullet$}
\drawvertex(Q){$\bullet$}
\drawvertex(R){$\bullet$}


\drawundirectededge(A,B){}\drawundirectededge(C,B){}\drawundirectededge(C,D){}\drawundirectededge(D,E){}\drawundirectededge(E,F){}
\drawundirectededge(F,G){}\drawundirectededge(G,H){}
\drawundirectededge(I,L){}\drawundirectededge(L,M){}\drawundirectededge(M,N){}\drawundirectededge(N,O){}\drawundirectededge(O,P){}
\drawundirectededge(P,Q){}\drawundirectededge(Q,R){}\drawundirectededge(D,N){$a$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\drawundirectedloop[t](G){}\drawundirectedloop[t](C){}
\drawundirectedloop[b](M){}\drawundirectedloop[b](Q){}

\drawundirectedcurvededge(A,B){}
\drawundirectedcurvededge(E,F){}\drawundirectedcurvededge(F,H){}

\drawundirectedcurvededge(R,P){}
\drawundirectedcurvededge(P,O){}\drawundirectedcurvededge(L,I){}
\put(107,60){$2^{\omega}$} \put(147,42){$0^{\omega}$} \put(147,74){$1^{\omega}$} \put(310,70){$\ldots$}\put(310,50){$\ldots$}\put(20,70){$\ldots$}\put(20,50){$\ldots$}

\small{\put(70,10){\textbf{Figure} 3. A finite portion of the 4-ended infinite Schreier graph}}
%\end{center}
\end{picture}


Observe that if $\xi \in E_i$ and $\eta \in E_j$, with $i\neq j$,
then $\Gamma_{\xi}$ and $\Gamma_{\eta}$ are not isomorphic.


Let us introduce some notation: 
let $\xi$ be an infinite word such that $\xi_n\in \{0,1\},
\xi\nsim 0^{\omega}, 1^{\omega}$. Notice that $\xi\in A(2)$, therefore
$\xi \in E_2$. From Theorem \ref{ends}, for any $k\neq 0$ one has $b^{k}(\xi)\neq \xi$ and $a^{k}(\xi)\neq \xi$ so that the
Schreier graph $\Gamma_{\xi}$ consist of two copies of the Cayley graph of
$\mathbb{Z}$ which intersect infinitely many times, together with some finite $a$-labeled subgraphs isomorphic to the finite polygons $\Upsilon_n$. It may happen that $v,w\in \Gamma_{\xi}$ and there is $k>0$, such that $b^k(v)=w$ and
$a(v)=w$. Given $\xi \in \{0,1\}^{\omega}$ we can associate with
it a (two-infinite) sequence $\{\xi(z)\}_{z\in\mathbb{Z}}$ of natural
numbers in the following way: 
\begin{enumerate}
  \item Take a copy of the graph of the Cayley graph of $\mathbb{Z}$ with generators $\pm 1$ and label the
  vertex 0 by 0 (corresponding to the vertex $\xi$).
  \item Label the vertex $m> 0$ by $k>0$ if $a^m(\xi)=b^k(a^{m-1}(\xi))$.
  \item Label the vertex $m< 0$ by $k>0$ if $a^m(\xi)=b^{-k}(a^{m+1}(\xi))$.
\end{enumerate}
We identify $\xi(z)$ with the label of $z$. Roughly speaking, the elements of the sequence
$\{\xi(z)\}_{z\in\mathbb{Z}}$ represent the steps made by
$b-$action to join consecutive $a-$connected elements. Since
$\xi\in \{0,1\}^{\omega}$ the sequence is well defined. For example, for $\xi=(01)^{\omega}$ (see Figure 4) one can easily verify that $\xi(1)=1,\xi(-1)=2, \xi(2)=5, \xi(-2)=1$ etc.

\begin{lem}\label{lemma2ends}
Let $\xi$ be an infinite word in $\{0,1\}^{\omega}$ such that
$\xi\nsim 0^{\omega}, 1^{\omega}$.
\begin{enumerate}
\item If $\xi$ starts by 0 then $\xi(2s+1)=1$ and $\xi(-2s)=1$ for
any $s\in \mathbb{N}$. If $\xi$ starts by 1 then $\xi(2s)=1$ and
$\xi(-2s+1)=1$ for any $s\in \mathbb{N}$.
\item If $a^{s}(\xi)=1^p0\xi_{p+2}\cdots$, $s>0$ then
$\xi(s+1)=\frac{3^p+1}{2}$.
\item If $a^{s}(\xi)=0^p1\xi_{p+2}\cdots$, $s<0$ then
$\xi(s-1)=\frac{3^p-1}{2}$.
\end{enumerate}
\end{lem}

\begin{proof} Part 1 follows from the fact that $a(0w)=1w=b(0w)$
and $a^{-1}(1w)=0w=b^{-1}(1w)$. Part 2 follows from the fact that
$a(1^p0\xi_{p+2}\cdots)$ = $b^{\frac{3^p+1}{2}}
(1^p0\xi_{p+2}\cdots)=0^p1\xi_{p+2}\cdots$. Part 3 is analogous to Part 2 for negative indices.
\end{proof}

\begin{prop}\label{prop2ends}
Let $\xi, \eta$ be infinite words in $\{0,1\}^{\omega}$ such that
$\xi, \eta\nsim 0^{\omega}, 1^{\omega}$. Then $\Gamma_{\xi}\simeq
\Gamma_{\eta} $ if and only if there exists $\gamma\in
\Gamma_{\eta}$ with either $\xi(z)=\gamma(z)$ $z\in \mathbb{Z}$, or
$\xi(z)=\gamma(-z)$ for any $z\in \mathbb{Z}$.
\end{prop}

\begin{proof} Identify $b\cdot \xi$ and $b\cdot \gamma$ with the graph of
$\mathbb{Z}$ in such a way that $\xi$ and $\gamma$ coincide with
0. Suppose that $\xi(z)=\gamma(z)$ (resp. $\xi(z)=\gamma(-z)$) for every $z$ and
define $\varphi:\Gamma_{\xi}\rightarrow\Gamma_{\eta}$ such that
$\varphi(\xi)=\gamma$ and $\varphi(v)=v$ (resp. $-v$), $v\in
\mathbb{Z}$. From Lemma \ref{lemma2ends} it is easy
to check that $\varphi$ is an isomorphism since the subgraph containing the vertices $v\in [a^t(\xi), a^{t+1}(\xi)]$, for any $t$, is uniquely determined.

On the other hand let $\varphi$ be an isomorphism between $\Gamma_{\xi}$ and $\Gamma_{\eta}$ such that $\varphi(\xi)=\gamma$. Suppose that there exists $z'\in \mathbb{Z}$, such that $|z'|$ is minimal and $\xi(z')\neq \pm \gamma(z')$. Assume that $z'>0$. By definition we have $a^{z'}(\xi)=b^{\xi(z')}a^{z'-1}(\xi)$. This implies $\varphi(b^{\xi(z')}a^{z'-1}(\xi))=\varphi(a^{z'}(\xi))=a^{z'}(\gamma)\neq b^{\gamma(z')}a^{z'-1}(\gamma)$. A contradiction.
\end{proof}

%\begin{figure}
%\includegraphics[scale=0.4]{schreier2ends}
%\caption{A 2-ended infinite Schreier graph of $G$}
%\end{figure}

\begin{center}
\begin{picture}(300,70)
 \setprofcurve{13}

\letvertex A=(35,40)\letvertex B=(65,40)\letvertex C=(95,40)\letvertex D=(125,40)\letvertex E=(155,40)\letvertex F=(185,40)\letvertex G=(215,40)\letvertex H=(245,40)\letvertex I=(3,50)\letvertex L=(255,50)


\drawvertex(A){$\bullet$}\drawvertex(B){$\bullet$}
\drawvertex(C){$\bullet$}\drawvertex(D){$\bullet$}\drawvertex(E){$\bullet$}
\drawvertex(F){$\bullet$}\drawvertex(G){$\bullet$}\drawvertex(H){$\bullet$}
\drawvertex(I){}\drawvertex(L){}


\drawundirectededge(A,B){}\drawundirectededge(C,B){}\drawundirectededge(C,D){}\drawundirectededge(D,E){}\drawundirectededge(E,F){}
\drawundirectededge(F,G){}\drawundirectededge(G,H){}


\drawundirectedloop[t](C){}\drawundirectedloop[t](F){}

\drawundirectedcurvededge(A,B){}
\drawundirectedcurvededge(B,D){}\drawundirectedcurvededge(D,E){}

\drawundirectedcurvededge(D,E){}\drawundirectedcurvededge(I,A){}
\drawundirectedcurvededge(E,L){}\drawundirectedcurvededge(G,H){}
\put(114,28){$(01)^{\omega}$}\put(258,48){$\cdot$}\put(260,48){$\cdot$ $a$}\put(250,40){$\ldots$ $b$}
\put(20,40){$\ldots$}
\small{
\put(50,10){\textbf{Figure} 4. A finite portion of a 2-ended infinite Schreier graph}}
\end{picture}
\end{center}

Let $\xi$ be an infinite word containing infinitely many 0 and 2
such that $\xi\nsim 0^{\omega}, 2^{\omega}$, i.e. $\xi \in E_1$.
In Section \ref{schreier} we remarked that $\xi\uparrow \Upsilon_n$ for
infinitely many $n$. More precisely, if $\xi_k=2$ and $h$ is the
first index greater than $k$ such that $\xi_h=0$, then
$\xi\uparrow \Upsilon_h$. Suppose that $\xi_1=2$ then we can associate
with $\xi$ an infinite sequence of polygons $\{\wp_i\}_{i\geq 1}\subseteq\{\Upsilon_i\}_{i\geq 1}$ such that
$\xi\uparrow \wp_i $ for any $i$ and the number of edges, or length, of $\wp_{i}$ is less
than the length of $\wp_{i+1}$. Moreover we can associate with $\xi$
a sequence $\{l_{\xi}(n)\}_{n\geq 1}$ where $l_{\xi}(k)=t$ if $\wp_k=\Upsilon_t$. More precisely,
any subword or block of $\xi$ of type $2w0, w\in \{1,2\}^n$, $0=\xi_t$
(i.e. $\underline{\xi}_t=2w0$, $w\in \{1,2\}^{t-2}$), gives rise to a new
element equal to $t$ in $\{l_{\xi}(n)\}_{n\geq 1}$,. Any
block of type $0w2,w\in \{0,1\}^n$ gives rise to $n+1$ elements
$(t,t+1,\ldots, t+n)$ in $\{l_{\xi}(n)\}_{n\geq 1}$ if $0=\xi_t$.

\begin{lem}\label{lemmapoligoni}
Let $\xi, \eta$ be infinite words containing infinitely many 0 and
2 such that $\xi, \eta \nsim 0^{\omega}, 2^{\omega}$. If for
any $h$ there exists infinitely many indices $n$ such that
$l_{\xi}(n)\neq l_{\eta}(n+h)$, then the graphs $\Gamma_{\xi}$ and
$\Gamma_{\eta}$ are not isomorphic.
\end{lem}

\begin{proof} Any vertex $\gamma\in  \Gamma_{\eta}$ is such that
the distance between $\eta$ and $\gamma$ is finite. This implies
the sequences $\{l_{\eta}(k)\}_{k\geq 1}$ and
$\{l_{\gamma}(k)\}_{k\geq 1}$ coincide up to a finite shifting of
the elements, since there exists a polygon $\Upsilon_n$ such that
$\eta,\gamma \uparrow \Upsilon_n$ and $\eta \sim \gamma$. 

If $\Gamma_{\xi}\simeq\Gamma_{\eta}$ and $\varphi$ is an
isomorphism such that $\varphi(\xi)=\gamma$ then the finite subgraph of $\Gamma_{\xi}$ induced by the vertices $v\in [0^{l_{\xi}(n)}\gamma_{l_{\gamma}(n)+1}\cdots $, $1^{l_{\xi}(n)}\gamma_{l_{\gamma}(n)+1}\cdots]$ has an isomorphic image in $\Gamma_{\gamma}$. Hence the distances of $\xi$ and $\gamma$ from $\{0^{l_{\xi}(n)}\xi_{l_{\xi}(n)+1}\cdot\cdot, 1^{l_{\xi}(n)}\xi_{l_{\xi}(n)+1}\cdot\cdot\}$ and $\{0^{l_{\gamma}(n)}\gamma_{l_{\gamma}(n)+1}\cdot\cdot, 1^{l_{\gamma}(n)}\gamma_{l_{\gamma}(n)+1}\cdot\cdot\}$, respectively, coincide for every $n$. This implies
that $l_{\xi}(n)=l_{\gamma}(n)$
for every $n$.
\end{proof}

Let $\xi$ be an infinite word as before. If $\wp_n$
is a polygon of length $2^t$ (i.e. $l_{\xi}(n)=t$), it contains
$0^t\xi_{t+1}\cdots$ and $1^t\xi_{t+1}\cdots$ (as vertices), and
such vertices are (among the vertices of the polygon) at maximal
distance with respect to the $b-$action. Looking at the graph
$\Gamma_{\xi}$, this means that $\xi\in [0^t\xi_{t+1}\cdots,
1^t\xi_{t+1}\cdots]$ for the infinitely many indices $t$'s such that
$l_{\gamma}(n)=t$.

We introduce the following sequence of binary vectors associated with $\xi$:
let $d_b$ denote the distance between two vertices in the graph
$\Gamma_{\langle b\rangle}$, where $\Gamma_{\langle b\rangle}$ is
the subgraph of $\Gamma_{\xi}$ with only $b-$labelled edges. Let
$\{d_n(\xi)\}_{n\geq 1}$ be a sequence where
$d_n(\xi)=(d_n^0(\xi), d_n^1(\xi))$ and $d_n^i(\xi)=d_b(\xi,
i^{l_{\xi}(n)}\xi_{l_{\xi}(n)+1}\cdots)$, for $i=0,1$. Roughly
speaking, the sequence $\{d_n(\xi)\}_{n\geq 1}$ measures the
$b-$distances of $\underline{\xi}_t$ from $0^t$ and $1^t$ in $\Gamma_t$ whenever
$\underline{\xi}_t$ is under the polygon $\wp_n$ of length $2^t$. The sequence
$\{d_n(\xi)\}_{n\geq 1}$ characterizes the one ended graphs.

%\begin{figure}
%\includegraphics[scale=0.4]{schreier1end}
%\caption{A 1-ended infinite Schreier graph of $G$}
%\end{figure}


\begin{center}
\begin{picture}(300,70)
 \setprofcurve{11}

\letvertex A=(33,30)\letvertex B=(63,30)\letvertex C=(93,30)\letvertex D=(123,30)\letvertex E=(153,30)\letvertex F=(183,30)\letvertex G=(213,30)\letvertex H=(243,30)\letvertex I=(18,40)\letvertex L=(253,40)


\drawvertex(A){$\bullet$}\drawvertex(B){$\bullet$}
\drawvertex(C){$\bullet$}\drawvertex(D){$\bullet$}\drawvertex(E){$\bullet$}
\drawvertex(F){$\bullet$}\drawvertex(G){$\bullet$}\drawvertex(H){$\bullet$}
\drawvertex(I){}\drawvertex(L){}


\drawundirectededge(A,B){}\drawundirectededge(C,B){}\drawundirectededge(C,D){}\drawundirectededge(D,E){}\drawundirectededge(E,F){}
\drawundirectededge(F,G){}\drawundirectededge(G,H){}


\drawundirectedloop[t](C){}\drawundirectedloop[t](F){}

\drawundirectedcurvededge(A,B){}
\drawundirectedcurvededge(G,H){}

\drawundirectedcurvededge(D,E){}
\setprofcurve{17} \drawundirectedcurvededge(B,G){}\drawundirectedcurvededge(I,L){}
\put(174,18){$(220)^{\omega}$}\put(255,38){$\cdot$ }\put(258,38){$\cdot$ }\put(248,30){$\ldots$}\put(15,38){$\cdot$ }\put(13,38){$\cdot$ }
\put(18,30){$\ldots$}\put(134,48){$a$}\put(134,60){$\vdots$}\put(263,30){$b$}
\small{
\put(20,5){\textbf{Figure} 5. A finite portion of a 1-ended infinite Schreier graph}}
\end{picture}
\end{center}



\begin{lem}\label{lemmapoligonidistanze}
Let $\xi, \eta$ be infinite words containing infinitely many 0 and
2 such that $\xi, \eta \nsim 0^{\omega}, 2^{\omega}$. Then
$\Gamma_{\xi}\simeq\Gamma_{\eta}$ if and only if there exists
$\gamma\in \Gamma_{\eta}$ such that for every $n\geq 1$ either
$d_{n}^i(\xi)=d_{n}^i(\gamma)$ or
$d_{n}^i(\xi)=d_{n}^{1-i}(\gamma)$, for $i=0,1$.
\end{lem}

\begin{proof} Let $\Gamma_{\xi}\simeq\Gamma_{\eta}$ and suppose there are infinitely many $n$
such that $d_n^i(\xi)\neq d_n^i(\gamma)$ and $d_n^i(\xi)\neq d_n^{1-i}(\gamma)$. If $\varphi(\xi)=\gamma$ then there exists $n$ large enough such that the balls of radius $\min \{d_{n}^0(\xi),d_{n}^1(\xi) \}$ centered at $\xi$ and $\gamma$ are not isomorphic. A contradiction.

On the other hand if either
$d_{n}^i(\xi)=d_{n}^i(\gamma)$ or
$d_{n}^i(\xi)=d_{n}^{1-i}(\gamma)$, then $\underline{\xi}_t$ and $\underline{\gamma}_t$ represent either the same vertex in $[0^t,1^t]$ or vertices of type $(\alpha_k, \beta_k)$ equal to $b^k(0^t)$ and $b^{-k}(0^t)$, for some $k>0$ (see Remark \ref{verticisimmetrici}). This implies that taking the sequence of (increasing in size)
balls of radius $\min \{d_{n}^0(\xi),d_{n}^1(\xi) \}$ (that goes to $\infty$ with $n$), these are
isomorphic.
\end{proof}

Given an infinite word $\theta$ such that $\theta_i\neq 2$ for every
$i$, we denote by $\overline{\theta}$ the word with
$\overline{\theta}_i=1-\theta_i$ for every $i$.

Given an infinite word $\eta$ such that $\eta_i\neq 0$ for every
$i$, we denote by $\overline{\overline{\eta}}$ the word with
$\overline{\overline{\eta}}_i=3-\eta_i$ for every $i$.



\begin{teo}\label{teoclass}
Let $G$ be the group defined above, then

\begin{itemize}
  \item $E_4$ consists of one orbit so there is only one 4-ended
  graph which coincides with a class of isomorphism.
  \item Let $\xi, \eta \in A(2)$, then there are uncountable many
  non isomorphic classes, each containing two orbital graphs:
  $\Gamma_{\xi}\simeq\Gamma_{\eta}$ if and only if $\xi\sim \eta$
  or $\xi \sim \overline{\eta}$.
  
  Let $\xi, \eta \in A(0)$, then there are uncountable many
  non isomorphic classes, each containing two orbital graphs:
  $\Gamma_{\xi}\simeq\Gamma_{\eta}$ if and only if $\xi\sim \eta$ or $\xi \sim \overline{\overline{\eta}}$.
\item Let $\xi, \eta \in E_1$, then there are uncountable many
  non isomorphic classes, each containing one or two orbital graph:
  $\Gamma_{\xi}\simeq\Gamma_{\eta}$ if and only if 
  $$\xi\sim 2x_1^1x_1^2\cdots x_1^{n_1}0y_1^1y_1^2\cdots y_1^{m_1}2x_2^1x_2^2\cdots x_2^{n_2}0y_2^1\cdots y_2^{m_2}2x_3^1 \cdots$$ with $x_i^j\in \{1,2\}$,
  $y_h^k\in \{0,1\}$ and $n_i, m_h\geq 0$; 
$$\eta\sim 2z_1^1z_1^2\cdots z_1^{p_1}0w_1^1w_1^2\cdots
w_1^{q_1}2z_2^1z_2^2\cdots z_2^{p_2}0w_2^1\cdots w_2^{q_2}2 z_3^1
\cdots$$ with $z_i^j\in \{1,2\}$
  and $w_h^k\in \{0,1\}$, $p_i, q_h\geq 0$; 
  such that:
\begin{enumerate}
  \item $n_i=p_i$ and $m_h=q_h$ for every $i,h$;
  \item either $z_i^j=x_i^j$ and $w_h^k=y_h^k$ or $z_i^j=\overline{\overline{x}}_i^j$ and $w_h^k=\overline{y}_h^k$ for every
  $i,j,h,k$.
\end{enumerate}


\end{itemize}

\end{teo}

\begin{proof} Since $E_4$ consists of one graph there is
nothing to prove.

Let $\xi \in E_2$. First we observe that if $\eta \in A(0)$ and
$\zeta\in A(2)$ then $\Gamma_{\eta}$ and $\Gamma_{\zeta}$ are not isomorphic because
$\Gamma_{\eta}$ does not contain any $a-$infinite orbit.

Let us study the case of $A(2)$. It is easy to prove from Lemma
\ref{lemma2ends} that $\xi$ and $\overline{\xi}$ give rise to
sequences such that $\xi(z)=\overline{\xi}(-z)$ for any
$\mathbb{Z}$. In fact, if $b^s(a^{k-1}(\xi))=a^k(\xi)$ then
$b^{-s}(a^{-(k-1)}(\overline{\xi}))=a^{-k}(\overline{\xi})$, so
that $\xi(k)=\overline{\xi}(-k)$. From Proposition \ref{prop2ends}
it follows that $\Gamma_{\xi}\simeq \Gamma_{\overline{\xi}}$. If
$\eta \nsim \xi$ or $\eta \nsim \overline{\xi}$ then there exists
infinitely many indices $i$ such that $\xi_i=\eta_i$ and
$\xi_{i+1}\neq \eta_{i+1}$. Without loss of generality assume, for example, that
$\xi_i=1$ and $\xi_{i+1}=1$. Suppose there exists an isomorphism
$\varphi$ between $\Gamma_{\xi}$ and $\Gamma_{\eta}$. Take $i$
large enough and let $k$ be such that
$a^{k-1}(\xi)=1^{i-1}\xi_i\cdots$ and
$a^{k-1}(\eta)=1^{i-1}\eta_i\cdots$. Hence from Lemma
\ref{lemma2ends} one has $\xi(k)\geq\frac{3^{i+1}+1}{2}$ and
$\varphi(\xi)(k)=\frac{3^i+1}{2}$. This is a contradiction.

Now suppose $\xi, \eta\in E_1$. Observe that, if the assumption
$(1)$ of the theorem is not valid, then Lemma \ref{lemmapoligoni}
applies and $\Gamma_{\xi}$ and $\Gamma_{\eta}$ are not isomorphic. Let us show that
given condition (1), $\Gamma_{\xi}\simeq \Gamma_{\eta}$ if and
only if condition $(2)$ is satisfied. It is enough to consider 
\begin{align*}
\xi&=2x_1^1x_1^2\cdots x_1^{n_1}0y_1^1y_1^2\cdots
y_1^{m_1}2x_2^1x_2^2\cdots x_2^{n_2}0y_2^1\cdots y_2^{m_2}2x_3^1
\cdots\text{ and }\\
\eta&=2z_1^1z_1^2\cdots z_1^{p_1}0w_1^1w_1^2\cdots
w_1^{q_1}2z_2^1z_2^2\cdots z_2^{p_2}0w_2^1\cdots w_2^{q_2}2 z_3^1
\cdots.
\end{align*}
 A letter $0$ after a sequence of $1,2$ gives rise to a
new polygon $\Upsilon_i$ such that $\xi\uparrow \Upsilon_i$ and $\eta\uparrow
\Upsilon_i$. In what follows we use Lemma \ref{lemmapoligonidistanze} and Remark \ref{verticisimmetrici}. Notice that
$l_{\xi}(i)=l_{\eta}(i)$ for every $i$, and so
$d^j_{i}(\xi)=d^j_{i}(\eta)$ ($j\in\{0,1\}$) if and only if
$\underline{\xi}_{l_{\xi}(i)}=\underline{\eta}_{l_{\eta}(i)}$ and $d^j_{i}(\xi)=d^{1-j}_{i}(\eta)$ ($j\in\{0,1\}$) if and only if
$$
\sum_{j=1}^{l_{\xi}(i)}
(\xi_j+\eta_j)3^{j-1}=\sum_{j=1}^{l_{\xi}(i)}3^{j-1}.
$$
Fixed $\xi$ the only two words satisfying the previous conditions
are those which satisfy condition $(2)$ of the theorem.

The proof about elements in $A(0)$ is analogous by considering
vectors of $b-$distances from $1^t\xi_{t+1}\cdots$ and
$2^t\xi_{t+1}\cdots$.
\end{proof}

\begin{os}\label{remarkfinale}\rm
We want to stress the fact that to establish the number of ends (and the isomorphism classes) of the vertices in $A(0)$, we have not used the properties of the group $G$, but only the structure of the graphs given by the construction. This means that, for such vertices, the same results hold independently of the choice of the base group acting on the binary tree (the binary adding machine in our case).
\end{os}

\subsection*{Acknowledgements}
The author warmly thanks Prof. Rostislav Grigorchuk for useful discussions. Moreover the author is grateful to the anonymous referees for comments and remarks that have certainly improved the presentation of the paper.

\begin{thebibliography}{99}


\bibitem{amenability bounded} L. Bartholdi, V. Kaimanovich and V. Nekrashevych, On amenability of automata groups, \textit{Duke Mathematical Journal}, \textbf{154}, No 3,  575--598, 2010.

\bibitem{hecketype} L. Bartholdi and R. Grigorchuk, On the spectrum of Hecke type operators related to some fractal
groups, {\it Tr. Mat. Inst. Steklova}, {\bf 231} , Din.
Sist., Avtom. i Beskon. Gruppy, 5--45; translation in {\it Proc.
Steklov Inst. Math.}, no. 4, 231, 1--41, 2000.

\bibitem{cucu} I. Bondarenko, T. Ceccherini-Silberstein, A. Donno and V. Nekrashevych, On a family of Schreier graphs of intermediate growth associated with a self-similar group, \textit{European Journal of Combinatorics},
\textbf{33}, Issue 7,  1408--1421, 2012.

\bibitem{BDN} I. Bondarenko, D. D'Angeli and T. Nagnibeda,  Ends of Schreier graphs of self-similar groups, in preparation.

\bibitem{bonda} I. Bondarenko and R. Kravchenko, Finite-state self-similar actions of nilpotent groups, \textit{Geometriae Dedicata}, Volume 163, Issue 1,  339--348, 2013.

\bibitem{basilica} D. D'Angeli, A. Donno,  M. Matter and T. Nagnibeda, Schreier
graphs of the Basilica group, \textit{Journal of Modern Dynamics},
 Vol. 4, no. 1, 167--205, 2010.

\bibitem{emanuele} D. D'Angeli and E. Rodaro, Groups and semigroups defined by colorings of synchronizing automata, \textit{International Journal of Algebra and Computation}, 1--21, 2014. \doi{10.1142/S0218196714500337} 

\bibitem{emanuele2} D. D'Angeli and E. Rodaro, A geometric approach to (semi)-groups defined by automata via
dual transducers, to appear in {\it Geometriae Dedicata}, 
%\doi{10.1007/s10711-014-0024-x}
\arxiv{1403.1722}

\bibitem{dynamicssubgroup} R. Grigorchuk, Some topics of dynamics of group actions on rooted trees,
\textit{The Proceedings of the Steklov Institute of Math.}, vol.
273, 1--118, 2011.

\bibitem{nonamenable} R. Grigorchuk and V. Nekrashevych, Amenable Actions of Nonamenable Groups, in Representation Theory, Dynamical Systems, Combinatorial and Algorithmic Methods. Part 13. ``Zapiski Nauchnyh
Seminarov POMI" Series, Vol. 326, 85--96, 2005.

\bibitem{savchuk} R. Grigorchuk and D. Savchuk, Self-similar groups acting essentially freely on the boundary of the binary rooted tree, To appear in {\it Contemporary Mathematics}, \textbf{611}, 9--48, 2014.

\bibitem{grizukprimo} R. Grigorchuk and A. \.{Z}uk, On the
asymptotic spectrum of random walks on infinite families of
graphs, {\it Random walks and discrete potential theory} (Cortona
1997), 188--204, Sympos. Math., XXXIX, Cambridge University Press,
Cambridge, 1999.

\bibitem{ihara} R. Grigorchuk and A. \.{Z}uk, The Ihara zeta function on infinite graphs, the KNS spectral measure and integrable maps, in
Random walks and geometry, Berlin, 141--180, 2004.

\bibitem{nekrashevyc} V. Nekrashevych, {\it Self-similar Groups}, Volume 117 of Mathematical Surveys and Monographs,
American Mathematical Society, Providence, RI, 2005.

\bibitem{nekra} V. Nekrashevych, Free subgroups in groups acting on rooted trees, \textit{Groups, Geometry, and Dynamics}, \textbf{4}, No. 4, 847--862, 2010.

\bibitem{sidki} S. Sidki, Automorphisms of one-rooted trees:
growth, circuit structure and acyclicity, {\it J. Math. Sci. (New
York)}, {\bf 100}, no. 1, 1925--1943, 2000.

\bibitem{vorobets} Y. Vorobets, Notes on the Schreier graphs of the Grigorchuk
group, in Dynamical Systems and Group Actions, L. Brown, R.
Grigorchuk, Y. Vorobets editors, AMS, Contemporary Mathematics,
vol. 567, 221--249, 2012.

\end{thebibliography}



\end{document} 