FWF Project P 29355-N35 Asymptotic Aspects and Automata in Group Theory

Responsable: Daniele D'Angeli E-mail: dangeli@math.tugraz.at Post-doc: Amnon Rosenmann E-mail: rosenmann@math.tugraz.at PhD: Abraham Gutierrez Sanchez E-mail: a.gutierrez@math.tugraz.at

Abstract

The proposed research consists of three main topics in geometric group theory: asymptotic isoperimetric functions on groups, asymptotic and probabilistic aspects in automaton groups, and formal languages associated with groups. In the spirit of modern research in geometric group theory, one of our purposes is to explore the possible connections between these themes, as such connections have recently led to some very interesting results. In automaton groups we intend to focus our attention on some algebraic properties. In particular, we want to find sucient conditions under which an automaton group is finitely generated. For this purpose we think that the explicit description of the corresponding virtual endomorphisms can be useful. From a more combinatorial point of view we want to study the geometric (and topological) structure of the corresponding innite Schreier graphs, extending the results known in the bounded case. These graphs usually reveal a sort of self-similar structure that we intend to exploit in order to study random walks on them. Innite Schreier graphs are determined by boundary stabilizers. In the case of bireversible (infinite) automaton groups, almost all boundary stabilizers are trivial. We plan to use the dual approach to show in this context the existence of non-trivial boundary stabilizers. In addition, we want to use the correspondence with \Wang tilings" to prove the undecidability of some problems in this setting. The Schreier graphs can also be interpreted in terms of powers of the dual automaton and this allows us to consider the class of languages recognized by them. We propose to give an algebraic characterization of automaton groups in terms of the languages recognized by their Schreier graphs, and also to characterize them in terms of a new class of recognition machines. In the study of isoperimetric functions of Cayley graphs of groups one is interested in the asymptotic behavior of the ratio between the boundaries or diameters of subgraphs and their "volumes". We plan to explore the notion of mean Dehn function through the use of random walks on Cayley graphs; dene the notion of Cheeger constant on groups instead of presentations of groups, and compute it on amalgamated products and other types; explore the relations between different isoperimetric and filling functions; compute the generalized isoperimetric profile. 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". Such groups are associated with the first topic through the study of the word problem on groups.

NEW

In the frame of our FWF-Project we are organizing the GAG workshop that will take place at TUGraz (11-12 Februar 2019)

Groups, Automata and Graphs (GAG)

Publications

Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter. On the Complexity of the Word Problem for Automaton Semigroups and Automaton Groups Advances in Applied Mathematics, Volume 90, September 2017, Pages 160-187, ISSN 0196-8858 Daniele D'Angeli, Alfredo Donno. Shuffling matrices, Kronecker product and Discrete Fourier Transform Discrete Applied Mathematics 233 (2017), 1-18. Daniele D'Angeli, Alfredo Donno. Wreath product of matrices Linear Algebra and its Applications 513 (2017), 276-303. Ievgen Bondarenko, Daniele D'Angeli, Tatiana Nagnibeda. Ends of Schreier graphs and cut-points of limit spaces of self-similar groups J. Fractal Geom. 4 (2017), no. 4, 369-424. Oliver Cooley, Abraham Gutiérrez. Multi-coloured jigsaw percolation on random graphs submitted D. D'Angeli, A. Donno and E. Rodaro, Catalan fragile words to appear in Int. J. Group Theory Asif Shaikh, Daniele D'Angeli, Hemant Bhate, Dilip Sheth. Galois coverings of Schreier graphs of groups generated by bounded automata submitted. Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter. Automaton Semigroups and Groups: on the Undecidability of Problems Related to Freeness and Finiteness submitted. D. D'Angeli, Th. Godin, I. Klimann, M. Picantin, E. Rodaro. Boundary action of automaton groups without singular points and Wang tilings submitted. Amnon Rosenmann, Franz Lehner, Aljosa Peperko. Polynomial convolutions in max-plus algebra submitted. Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter. On the Structure Theory of Partial Automaton Semigroups submitted. Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter. Orbit Expandability of Automaton Semigroups and Groups submitted. Daniele D'Angeli, Dominik Francoeur, Emanuele Rodaro, Jan Philipp Wächter. Orbits of Automaton Semigroups and Groups submitted. Matteo Cavaleri, Daniele D'Angeli and Alfredo Donno. Permutational powers of a graph submitted.

Collaborators and visitors

Emanuele Rodaro, Polimi (November 2017, February 2018) Jan Philipp Wächter, Univ. of Stuttgart (November 2017) Aitor Perez, Univ. Geneva (January 2018) Enric Ventura Capell, Univ. Politecnica de Catalunya (February 2018) Francesco Matucci, Bicocca Milano (May 2019)