FWF - AAAGT - Asymptotic Aspects and Automata in Group Theory

The research project is about exploring several topics in the Mathematical field of geometric group theory. In the spirit of modern research in geometric group theory, mainly influenced by the work of Gromov from the 1980's and on, one of our purposes is to explore the possible connections between these topics, as such connections have recently led to some very interesting results. An interesting class of groups in which graphs appear in an algebraic context is that of automaton groups. These groups are generated by automata and act by automorphisms on rooted trees. They were introduced in the early 1980's when Grigorchuk constructed the first example of a group of intermediate growth (a problem posed by Milnor). It was discovered that very simple automata may generate groups with exotic properties that are hard to be found in classically-defined groups. Nekrashevych highlighted a very surprising connection between such groups and complex dynamics, consequently solving difficult dynamics problems by algebraic methods. We plan to find conditions under which an automaton group is finitely presented and to characterize some geometrical properties of the corresponding Schreier graphs (in terms of growth, number of ends, isomorphism problem). By interpreting the Schreier graphs in terms of complete automata, we want to study the class of languages recognized by them. When given a presentation of a group, one can associate with it a graph (the Cayley graph) and study geometric, algorithmic and dynamical aspects of the group through this graph. The asymptotic isoperimetric functions on Cayley graphs refer to the asymptotic behavior of the ratio between the boundaries or diameters of subgraphs and their “volumes”. We want to explore one of these less studied asymptotic functions, mean Dehn function, through random walks. Another asymptotic function, Cheeger constant, which has applications in computer networking, is defined on graphs analogously to its definition on Riemannian manifolds. However, the definition refers to presentations of groups and our aim is to define and compute it on groups. We also want to explore what types of languages and automata have “good” algorithmic properties and are suited for extending the class of “graph automatic groups”.