Problem of the Week
Hilton Memorial Lecture
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.