  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.
