Combinatorial Landscapes

Abstract

Abstract. Fitness landscapes have proven to be a valuable concept in evolutionary biology, combinatorial optimization, and the physics of disordered systems. A fitness landscape is a mapping from a configuration space into the real numbers. The configuration space is equipped with some notion of adjacency, nearness, distance or accessibility. Landscape theory has emerged as an attempt to devise suitable mathematical structures for describing the “static ” properties of landscapes as well as their influence on the dynamics of adaptation. In this review we focus on the connections of landscape theory with algebraic combinatorics and random graph theory, where exact results are available.