Using Lexicographical Orderings to Find Automatic Structures

11/15/2011 - 12:15pm
11/15/2011 - 1:10pm
Rena Levitt (Pomona College)

It is a well understood principle in geometric group theory that there is a close connection between the intrinsic geometry of a topological space and the computation properties of its fundamental group. This connection led to the development of the theory of automatic groups by Cannon and Thurston in the late 1980’s. A group G is automatic if there exists a regular language L mapping onto G whose path distance in the Cayley graph of G is small. From the language L, we can build an automatic structure for G that completely determines right multiplication for the group.  In practice, finding such a language that is both regular and behaves well with respect to the path metric can be quite challenging. It is often useful to find a cellular complex C that G acts on geometrically, and study the edge paths in C. In this talk I will discuss using a lexicographical ordering on the vertices of the complex  C to determine the regular language L. In particular, I will show that groups acting on weakly systolic complexes are automatic by using an ordering on the vertices given by a lexicographical breadth first search.

ML 134