Growth Without Groups
(Growth in Nonsymmetric Graphs: Computation and Asymptotics)
Abstract
The ball growth b(n) from a vertex v in a graph G counts the
number of vertices that can be reached from v by paths of length n or less;
the sphere growth s(n) is defined similarly with paths of length exactly n.
If G is the Cayley graph for a group A with finite generating set X, the
asymptotic equivalence class for b(n), given a somewhat unusual definition of
asymptotic equivalence, is independent of the choice of generating set and
is called the growth of the group A (Milnor, Bass, Gromov, et al.). The
theory for growth in vertex transitve graphs parallels that for groups
(Trofimov, Imrich, Seifter, et al.). This joint work with Tomo Pisanski
begins a study of growth in general graphs. To provide specific
computational examples, ways of combining graphs are introduced that are
analogous to group constructions, such as free products. To provide a
foundation for asymptotic analysis, the two natural kinds of asymptotic
equivalence are compared. A mild condition is introduced that ensures
asymptotic equivalence for sphere growth from different vertices.
Connections to isoperimetric inequalities and transience in random walks on
graphs are also discussed.
R E F R E S H M E N T S
4:00 To 4:25 PM
Kenneth W. Anderson
Memorial Reading Room
