The Characterization of Fixed Points in a Sequential Dynamical System

Jame Duvall

Graph dynamical systems are central to the modeling of a wide range of different phenomena on networks. As a particular type of graph dynamical systems, sequential dynamical systems (SDS) have numerous applications ranging from disease dynamics to the mapping of traffic flows. These applications also extend to modeling cellular automata (CA), which have a lot in common, structurally, with SDS. The goal of this paper is to thoroughly examine one of the most commonly studied graph structures, the circle graph, which is denoted by Circn. Using some function f3 : {0,1}3 --> {0,1}, the process of characterizing fixed points over this graph is delineated and the specific outcomes for each result are then discussed. Specifically, this paper will examine a special case, the majority function which is denoted by maj3, and the outcomes it produces when applied to Circn. In general, computing these fixed points for an arbitrary graph is hard and computationally intractable. Therefore, the final portion of this paper will discuss the wheel graph, denoted Wheeln, and the impending complications that arise when attempting to compute its local fixed points.