Equitable Partitions, Coherent Algebras and Random Walks: Applications to the Correlation Structure of Landscapes


Peter F. Stadler, Gottfried Tinhofer

Submitted to MATCH

A landcape is a fitness function f:V ->R defined on the vertex set V of a configuration graph G. The pair (G,f) is a mathematical model for studying functions on a discrete set $V$ where the neighborhood relation on the graph defines how one is able to move within this set and get access to the values of f. There are many situations where such a model is of high interest, in chemistry and elsewhere. Configuration spaces im molecular biology, spin glass models in physics, QSAR models in chemistry or pharmacology are landscapes in our sense, as well as the solution spaces of combinatorial optimization problems together with a solution heuristic like simulated annealing or some version of a genetic algorithm are a few examples. Autocorrelation functions are strong mathematical tools for a profound study of landscapes. These functions are defined in terms of random walks on G and represented conveniently either using eigenvalues and eigenspaces of the configuration graphs G or via equitable partitions derived from its coherent algebra. In this paper we give a comprehensive introduction into the use of equitable partitions for investigating spectral properties of typical configuration graphs. The techniques demonstrated here are certainly useful in a wide range of applications in chemistry, not only in the study of landscapes. Further we present some basic notions from the theory of coherent algebras and show how they enable us to work out a rich panel of autocorrelation functions for a fixed fitness function f.

Return to 1999 working papers list.