% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % 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} % use these commands for typesetting doi and arXiv references in the bibliography %\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} %\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments %\documentclass[a4paper,12pt]{amsart} \usepackage{graphicx} \usepackage{amssymb} \usepackage{amsmath} \usepackage{latexsym} \usepackage{amsthm} \usepackage{latexsym,bezier,gastex,amsbsy,enumerate,amsfonts,amsmath,amscd,amssymb,setspace,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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Schreier graphs of an extended version \\ of the binary adding machine} %\footnotetext{The author was supported by Austrian Science Fund project FWF P24028-N18} \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)}\\ \small{Technische Universit\"{a}t Graz, Austria.}\\ %Tel. +43 (316) 873 - 7631\\ \small{dangeli@math.tugraz.at}} \date{\dateline{Oct 13, 2014}\\ \small Mathematics Subject Classifications: 20E08, 20F69, 37E25 } \unitlength=0,4mm %\title{\bf An elementary proof\\ of the reconstruction conjecture} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \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. \bigskip \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. The trichotomy given by V. Nekrashevych in \cite{nekra} can be used in this setting to establish the absence of free subgroups in $G$. 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 subgroup dynamics \cite{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$} \tiny{ \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$} \tiny{ \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 vertex and edge sets 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$} \tiny{ \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 $v0$ 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. $v0$, 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$} \tiny{ \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$} \tiny{ \put(51,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\\ $\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$ 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$. 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, Infinite Schreier graphs of the Basilica group, \textit{Journal of Modern Dynamics}, \textbf{24}, Vol. 2, 153--194, 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} \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}