Personal tools

An Example of an Automatic Graph of Intermediate Growth

— filed under:

Dmytro Savchuk, University of South Florida

  • Topology Seminar
When Fri, Mar 22, 2013
from 11:00 AM to 11:50 AM
Where Ritter 316
Add event to calendar vCal

Abstract: We give the first example of a 4-regular in finite automatic graph of intermediate growth. It is constructed as a Schreier graph of a group generated by 2-state Mealy automaton. In the first half of the talk we will review the notion of groups generated by automata and explain why this class of groups is interesting. Then we will recall the well-established notion of an automatic group (which is different from a group generated by automaton). The class of automatic groups is important, in particular, because it admits many computational routines. On the other hand, many groups are not automatic. A wider class of Cayley automatic groups was recently introduced by Kharlampovich, Khoussainov and Miasnikov. One of the open questions about this class is whether it contains groups of intermediate growth (i.e. groups whose growth functions grow faster than any polynomial and slower than exponential function). The example that we construct could potentially serve as a basis for answering this question.  This work is joint with Alexei Miasnikov.

« September 2017 »