The Cayley graph of a group G with respect to a set of generators A is the graph whose vertices are the elements of G, and such that for each g in G and each generator a in A, an edge runs from g to ga labeled with the generator a. This graph has topological and geometric properties which are often related to properties of the group G and independent of the set of generators. Gromov's notion of "negatively curved" group, for example, can be stated in terms of the Cayley graph as saying that there is a fixed number c such that in each triangle of shortest paths in the Cayley graph, each edge of the triangle is within the c-neighborhood of the union of the other two edges. There are various other properties which can be described in similar terms, although the definitions are not quite so simple, usually. One of the most interesting is a property invented by Stephen G. Brick which he calls "qsf"; given a group-presentation, one constructs the 2- complex which is described, having the given group as fundamental group; one asks whether arbitrarily large neighborhoods of the identity in the universal cover can be faithfully represented (in a certain technical sense) by finite, 1-connected complexes mapping into the universal cover; if so, the group is said to be "quasi- simply-filtrated" or qsf. There are generalizations of some results of Poenaru and Casson, so that one has a theorem to the effect that if an aspherical, P2-irreducible, closed 3-manifold has fundamental group which is qsf, then its universal cover is homeomorphic to R3. These and related notions have produced a revolution in the theory of infinite groups within the last few years. The basic pattern seems to be that one finds some facts in differential geometry and topology of 3-manifolds; one abstracts to the fundamental group level, and then one finds group-theoretic theorems which sometimes have a reverse application to topology. In addition, the subject tends to have a connection with the computability of the Cayley graph itself; the Todd-Coxeter algorithm for finite groups thus extends to various kinds of computability questions about finite Cayley graphs. The theory of "automatic groups" involves finite-state automata and regular languages; this theory, however, does not apply to certain easily understood groups such as nilpotent groups and matrix groups over the integers; in order to understand these, one needs to extend the notion of a finite-state machine in certain very restricted ways which are not yet obvious. Perhaps this will have implications in formal language theory and other aspects of mathematics usually considered to be "computer science."

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Application #
9203941
Program Officer
Ralph M. Krause
Project Start
Project End
Budget Start
1992-08-01
Budget End
1995-07-31
Support Year
Fiscal Year
1992
Total Cost
$123,900
Indirect Cost
Name
University of California Berkeley
Department
Type
DUNS #
City
Berkeley
State
CA
Country
United States
Zip Code
94704