Random graph gauge theories as toy models for non-perturbative string theories

We present simple models which exhibit some of the remarkable features expected to hold for the as yet unknown non-perturbative formulation of string theories. Among these are: (a) the absence of a background or embedding space for the full theory; (b) perturbative ground states (local minima of the action) having the characteristics of spaces of different dimension; (c) duality transformations between large- and small-coupling expansions; and (d) perturbative excitations of these ground states which can be interpreted as string worldsheets or p-brane worldvolumes. In this context we formulate gauge theories on arbitrary graphs and speculate concerning actions for graphs which in a continuum and/or thermodynamic limit might be related to the Einstein-Hilbert action.