GRAPH SUBSTITUTIONS

In 1984, Gromov (see [4] and [6]) introduced the idea of subdividing a 'branching' polyhedron into smaller cells and replacing these cells b y more complex objects, reminiscent of the growth of multicellular org anisms in biology. The simplest situation of this kind is a graph subs titution which replaces certain subgraphs in a graph G by bigger finit e graphs. The most basic graph substitution is a vertex replacement ru le which replaces certain vertices of G with finite graphs. This paper develops a framework for studying vertex replacements and discusses t he asymptotic behavior of iterated vertex replacements, the limit obje cts, and the induced dynamics on the space of infinite graphs from the viewpoint of geometry and dynamical systems.