Graph substitutions

Abstract

In 1984, Gromov (see [4] and [6]) introduced the idea of subdividing a ‘branching’ polyhedron into smaller cells and replacing these cells by more complex objects, reminiscent of the growth of multicellular organisms in biology. The simplest situation of this kind is a graph substitution which replaces certain subgraphs in a graph $G$ by bigger finite graphs. The most basic graph substitution is a vertex replacement rule which replaces certain vertices of $G$ with finite graphs. This paper develops a framework for studying vertex replacements and discusses the asymptotic behavior of iterated vertex replacements, the limit objects, and the induced dynamics on the space of infinite graphs from the viewpoint of geometry and dynamical systems.