Graph automaton groups

Algebraic structures can be usually described by means of their combinatorial nature. A typical example is the relation between groups and graphs. In Geometric Group Theory, for instance, many algebraic properties of a group can be detected by investigating the combinatorial properties of the corresponding Cayley graphs. Another typical example of this interaction is achieved by the automaton group theory. Automata (or Mealy machines or transducers) are directed graphs whose transitions describe the action of the states on a finite alphabet. If, for instance, the automaton is complete and invertible, then its states generate a group that has, in many cases, very interesting properties.
As an example, in 1980 R. I. Grigorchuk described in [20] the first group of intermediate (i.e., faster than polynomial and slower than exponential) growth, that later appeared to be generated by a finite automaton. This group has a number of other interesting properties: for example, it is infinite and finitely generated, but each of its elements has finite order (Burnside group). It was also the first example of an amenable but not elementary amenable group. Over the last decades, a new exciting direction of research focusing on finitely generated automaton groups acting by automorphisms on rooted trees has been developed. It turned out that it has deep connections with the theory of profinite groups and with complex dynamics. The interested reader can refer for more details to the following list of works (and bibliography therein) [1, 2, 21, 27]. Recently a special interest has been pointed out for decision problems for automaton groups and semigroups (see [16, 18, 19, 29] and references therein).
Beside Cayley graphs the best way to encode the action of automaton groups is given by the structure of the corresponding Schreier graphs. These graphs better represent the length-preserving action of an infinite automaton group on a finite alphabet and constitute an infinite sequence of finite graphs converging to infinite graphs in the Gromov-Hausdorff topology. Finite Schreier graphs can be regarded as orbital graphs with respect to the action of the automaton group on each level of a regular rooted tree, whereas their limits are orbital graphs of the action of the group on the boundary of the tree. Finite Schreier graphs have been studied from a combinatorial point of view in several contexts (e.g., the investigation of models coming from Statistical Mechanics [13, 14]). Classification of infinite Schreier graphs have been studied in several papers (see [6, 7, 11, 12, 15, 23] for further discussions about this topic).

In this paper, we introduce a family of automaton groups arising from finite graphs, that we call graph automaton groups (Definition 3.1). More precisely, with any finite graph $G=(V,E)$, we associate an invertible automaton $\mathcal{A}_{G}$ whose state set is identified with the edge set $E$ and that acts on words over an alphabet identified with the vertex set $V$. Basically, any edge has a nontrivial action only on words starting with a letter identified with one of its endpoints. In this way, we can define an automaton that has the remarkable property of being bounded. The class of bounded automaton groups is very popular and it contains the most famous examples of automaton groups (e.g., the Grigorchuk group and the Basilica group [25]). It is a remarkable fact that all groups generated by bounded automata are amenable, and so all our graph automaton groups have this property. It is interesting that, with our construction, we recover some classical examples of automaton groups (e.g., the Adding machine and the Tangled odometer group, see Example 3.1). Among other properties, we prove that our groups are fractal and weakly regular branch over their commutator subgroup (Theorem 3.1), that they all contain (except some trivial cases) a free semigroup (Theorem 3.2) and so they have exponential growth (Corollary 3.1). We also highlight a connection between our groups and the right-angled Artin groups (Proposition 3.4).
The second part of the paper is devoted to the investigation of the Schreier graphs associated with the action of graph automaton groups. In Theorem 4.1, we give a rigidity result for the automorphism group of Schreier graphs when the initial graph is cyclic. Then we present an explicit recursive description of the Schreier graphs of graph automaton groups generated by path graphs, and we are able to determine their diameter (Theorem 4.2) and their automorphism group (Theorem 4.3).

We recall in this preliminary section some basic definitions and properties about automaton groups and growth.

The automaton $\mathcal{A}$ is finite if $S$ is finite and it is invertible if, for all $s\in S$, the transformation $\mu(s,\cdot):X\rightarrow X$ is a permutation of $X$. An automaton $\mathcal{A}$ can be visually represented by its Moore diagram: this is a directed labeled graph whose vertices are identified with the states of $\mathcal{A}$. For every state $s\in S$ and every letter $x\in X$, the diagram has an arrow from $s$ to $\lambda(s,x)$ labeled by $x|\mu(s,x)$. A sink $id$ in $\mathcal{A}$ is a state with the property that $\lambda(id,x)=id$ and $\mu(id,x)=x$ for any $x\in X$.

An important class of automata is given by the so-called bounded automata [28]. An automaton is said to be bounded if the sequence of numbers of paths of length $n$ avoiding the sink state (along the directed edges of the Moore diagram) is bounded.

For each $n\geq 1$, let $X^{n}$ denote the set of words of length $n$ over the alphabet $X$ and put $X^{0}=\{\emptyset\}$, where $\emptyset$ is the empty word. The action of $\mathcal{A}$ can be easily extended to the infinite set $X^{\ast}=\bigcup_{n=0}^{\infty}X^{n}$ as follows:

for every $w\in X^{\ast}$. For a state $s\in S$, we denote by $\mathcal{A}_{s}$ the transformation $\mu(s,\cdot)$ on $X^{\ast}$ defined by Eqs. (1), which is a bijection if $\mathcal{A}$ is invertible. Given the invertible automaton $\mathcal{A}$, the automaton group generated by $\mathcal{A}$ is by definition the group generated by the transformations $\mathcal{A}_{s}$, for $s\in S$, and it is denoted $G(\mathcal{A})$. In the rest of the paper, we will often use the notation $s$ instead of $\mathcal{A}_{s}$. Moreover, the maps $\lambda$ and $\mu$ can be naturally extended to each element of $G(\mathcal{A})$. Notice that the action of $G(\mathcal{A})$ on $X^{\ast}$ preserves the sets $X^{n}$, for each $n$.
It is a remarkable fact that an automaton group can be regarded in a very natural way as a group of automorphisms of the regular rooted tree of degree $|X|=k$, i.e., the rooted tree $T_{k}$ in which each vertex has $k$ children, via the identification of the $k^{n}$ vertices of the $n$-th level of $T_{k}$ with the set $X^{n}$.
The group $G(\mathcal{A})$ is said to be spherically transitive if its action is transitive on $X^{n}$, for any $n$. Let $g\in G(\mathcal{A})$. The action of $g$ on $X^{\ast}$ can be factorized by considering the action on $X$ and $|X|$ restrictions as follows. Let $Sym(k)$ be the symmetric group on $k$ elements. Then an element $g\in G(\mathcal{A})$ can be represented as

where $g_{i}:=\lambda(g,i)\in G(\mathcal{A})$ and $\sigma\in Sym(k)$ describes the action of $g$ on $X$. We say that Eq. (2) is the self-similar representation of $g$. Notice that, given $g=(g_{1},\ldots,g_{k})\sigma$ and $h=(h_{1},\ldots,h_{k})\tau$, the self-similar representation of $gh$ is

In the tree interpretation of Eq. (2), the permutation $\sigma$ corresponds to the action of $g$ on the first level of $T_{k}$, and the automorphism $g_{i}$ is the restriction of the action of $g$ to the subtree (isomorphic to $T_{k}$) rooted at the $i$-th vertex of the first level.

Let us denote by $Stab_{G(\mathcal{A})}(X)=\{g\in G(\mathcal{A}):g(x)=x,\ \forall\ x\in X\}$ the stabilizer of $X$, that is, the subgroup of $G(\mathcal{A})$ consisting of all elements acting trivially on $X$. In particular, if $g\in Stab_{G(\mathcal{A})}(X)$, then one can identify $g$ with the $k$-tuple $(g_{1},\ldots,g_{k})$, where $g_{i}=\lambda(g,i)$.

Given two groups $G_{1}$ and $G_{2}$, the direct product of $G_{1}$ and $G_{2}$ will be denoted by $G_{1}\times G_{2}$. In particular, we denote by $G^{k}$ the $k$-times iterated direct product of a group $G$ with itself. The following definitions are given in the literature for the broader class of self-similar groups (see [27]). Here we restrict our interest to automaton groups.

Let $\mathcal{G}$ be a finitely generated group, with symmetric generating set $S=S^{-1}$. The length of $g$ with respect to $S$ is denoted by $|g|_{S}$ (we will omit the subscript $S$ when the generating set is fixed) and it is defined as the minimal length of a word in $S^{\ast}$ representing the element $g$. Then one puts $\gamma_{S}(n)=\#\{g\in\mathcal{G}:|g|_{S}\leq n\}$. This defines the growth function

This map clearly depends on the generating set $S$. However, one can prove that changing the generating set does not affect the asymptotic properties of $\gamma_{S}$. In particular, the growth rate

is greater than or equal to $1$ independently on the particular generating set (see, for instance, [17]).

We present in this section the main construction of the paper, that is, we are going to associate an invertible automaton with a given finite graph.
Let $G=(V,E)$ be a finite graph. Let $V=\{x_{1},\ldots,x_{k}\}$ (we will often use also the notation $\{1,2,\ldots,k\}$) be its vertex set and let $E$ be its edge set.
First of all, we choose an orientation for the edges of $G$. Let $E^{\prime}$ be the set of edges, where an orientation of each edge has been chosen. Notice that elements in $E$ are unordered pairs of type $\{x_{i},x_{j}\}$, whereas elements in $E^{\prime}$ are ordered pairs of type $(x_{i},x_{j})$, meaning that the edge has been oriented from the vertex $x_{i}$ to the vertex $x_{j}$.
We then define an automaton $\mathcal{A}_{G}=(E^{\prime}\cup\{id\},V,\lambda,\mu)$ such that:

• •

  $E^{\prime}\cup\{id\}$ is the set of states;

• •

  $V$ is the alphabet;

• •

  $\lambda:E^{\prime}\times V\to E^{\prime}$ is such that, for each $e=(x,y)\in E^{\prime}$, one has

  $$\lambda(e,z)=\left\{\begin{array}[]{ll}e&\hbox{if }z=x\\ id&\hbox{if }z\neq x;\end{array}\right.$$

• •

  $\mu:E^{\prime}\times V\to V$ is such that, for each $e=(x,y)\in E^{\prime}$, one has

  $$\mu(e,z)=\left\{\begin{array}[]{ll}y&\hbox{if }z=x\\ x&\hbox{if }z=y\\ z&\hbox{if }z\neq x,y.\end{array}\right.$$

In other words, any directed edge $e=(x,y)$ represents a state of the automaton $\mathcal{A}_{G}$ and it has just one restriction to itself (given by $\lambda(e,x)$) and all other restrictions to the sink $id$. Its action is nontrivial only on the letters $x$ and $y$, which are switched since $\mu(e,x)=y$ and $\mu(e,y)=x$. It is easy to check that $\mathcal{A}_{G}$ is invertible for any $G$ and any choice of the orientation of the edges. This makes us able to define an associated automaton group.

The previous remark basically says that we can just consider simple graphs. We make from now on this assumption. The following proposition shows that the graph automaton group $\mathcal{G}_{G}$ does not depend on the particular orientation of the edges in $G$ nor on the order of the vertices in $V$.

In the light of Proposition 3.1, given an oriented edge $e=(x_{i},x_{j})\in E^{\prime}$, we can denote by $e^{-1}=(x_{j},x_{i})$ the edge with the opposite orientation, keeping in mind that the choice of the opposite orientation corresponds to take the inverse in $\mathcal{G}_{G}$.

The following result shows that taking subgraphs in $G$ corresponds to obtain subgroups in $\mathcal{G}_{G}$. By a subgraph of $G$, here we mean a subset of its edges, together with the subset of vertices of $V$ consisting of their endpoints.

By virtue of Proposition 3.3, we can suppose $G$ to be connected. Therefore, from now on, we assume $G=(V,E)$ to be simple and connected.

Notice that if $e,f\in E^{\prime}$ do not share any vertex, then $[e,f]=e^{-1}f^{-1}ef=id$ in $\mathcal{G}_{G}$, since their actions are nontrivial on disjoint subsets of $V$. The next theorem collects some more algebraic properties shared by (almost) all graph automaton groups.
A directed path of length $t$ from the vertex $v$ to the vertex $w$ in a graph $G=(V,E)$ is a sequence of vertices $v_{i_{0}}=v,v_{i_{1}},v_{i_{2}},\ldots,v_{i_{t}}=w$ in which all edges $e_{1},e_{2},\ldots,e_{t}$ are oriented in the direction from $v$ to $w$, that is, one has $e_{1}=(v,v_{i_{1}}),e_{2}=(v_{i_{1}},v_{i_{2}}),\ldots,e_{t}=(v_{i_{t-1}},w)$. A directed cycle of length $t$ is a directed path such that $v_{i_{0}}=v_{i_{t}}$.

If we consider the Case (1) in Example 3.1, where the initial graph contains only one edge, it gives rise to the Adding machine. This group is fractal but it is abelian, free and not weakly regular branch. Basically, this is the only nontrivial case for which the properties (2)-(4) of Theorem 3.1 do not hold.

Let us focus now on the semigroup structure of graph automaton groups. This will allow to know the growth of graph automaton groups (see Corollary 3.1).

In this section we recall the notion of Schreier graphs and we study some properties of them in the context of graph automaton groups.
Let $\mathcal{G}$ be a finitely generated group with a set $S$ of generators such that $id\not\in S$ and $S=S^{-1}$, and suppose that $\mathcal{G}$ acts on a set $M$. Then one can consider a graph $\Gamma(\mathcal{G},S,M)$ with vertex set $M$, where two vertices $m,m^{\prime}$ are joined by an edge if there exists $s\in S$ such that $s(m)=m^{\prime}$. If this is the case, we label the edge from $m$ to $m^{\prime}$ by $s$, and the edge from $m^{\prime}$ to $m$ by $s^{-1}$. Equivalently, we can think that the same (undirected) edge is labeled by $s$ near $m$ and by $s^{-1}$ near $m^{\prime}$.
If the action of $\mathcal{G}$ on $M$ is transitive, then the graph $\Gamma(\mathcal{G},S,M)$ is connected and corresponds to the classical notion of Schreier graph $\Gamma(\mathcal{G},S,Stab_{\mathcal{G}}(m))$ of the group $\mathcal{G}$ with respect to the stabilizer subgroup $Stab_{\mathcal{G}}(m)$ for some (any) $m\in M$ (see [27]).

Notice that, although Schreier graphs are defined as directed and labeled graphs, for our purposes we will often consider them as undirected and unlabeled graphs.

In what follows, we denote by $\Gamma_{n}^{G}$ the $n$-th Schreier graph of the graph automaton group $\mathcal{G}_{G}$. The vertex set of $\Gamma_{n}^{G}$ is identified with $V^{n}$, where $G=(V,E)$. Observe that $\Gamma_{1}^{G}$ coincides with $G$ up to remove loops and multi-edges from $\Gamma_{1}^{G}$. Therefore, we can say that $\Gamma_{1}^{G}$ and $G$ coincide as simple graphs. Moreover, the Schreier graph $\Gamma_{n}^{G}$ is a regular graph of degree $2|E|$ by definition.

The Schreier graph $\Gamma_{n}^{G}$ only depends on the initial graph $G=(V,E)$ and not on the orientation of its edges, since the generating set that we let act on $V^{n}$ is supposed to be symmetric. The following lemma is well known [1].

We are going to show how cut-vertices in $G$ propagate in the Schreier graphs $\Gamma_{n}^{G}$. Recall that a cut-vertex of a graph is a vertex whose deletion increases the number of connected components of the graph (see, for instance, [4]). Observe that, for our purposes, when we delete a cut-vertex from a graph we do not remove the edges which are incident to that vertex. We need some technical preparation.
Let $x$ be a cut-vertex of $G$, whose deletion disconnects $G$ into $c$ connected components $G_{1},\ldots,G_{c}$ with $G_{i}=(V_{i},E_{i})$ for each $i=1,\ldots,c$. If a vertex $v$ of $V^{n}$ has the form $v=x^{k}yv^{\prime}$, with $k\geq 1$, and $y\in V_{i}$, then a special subgraph of $\Gamma_{n}^{G}$ associated with the vertex $v$ can be constructed as follows.