## 99-NN-003

#
Abstract:

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

[PostScript]

##
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.