Reduction Of Discrete Dynamical Systems Over Graphs

In this paper we study phase space relations in a certain class of discrete dynamical systems over graphs. The systems we investigate are called Sequential Dynamical Systems (SDSs), which are a class of dynamical systems that provide a framework for analyzing computer simulations. Specifically, an SDS consists of (i) a finite undirected graphYwith vertex set{1,2,…,n}where each vertex has associated a binary state, (ii) a collection ofY-local functions(Fi,Y)i∈v[Y]with$F_{i,Y}: \mathbb{F}_2^n\to \mathbb{F}_2^n$and (iii) a permutation π of the vertices ofY. The SDS induced by (i)–(iii) is the map\[ [F_Y,\pi] = F_{\pi(n),Y} \circ \cdots \circ F_{\pi(1),Y}\,. \]The paper is motivated by a general reduction theorem for SDSs which guarantees the existence of a phase space embedding induced by a covering map between the base graphs of two SDSs. We use this theorem to obtain information about phase spaces of certain SDSs over binary hypercubes from the dynamics of SDSs over complete graphs. We also investigate covering maps over binary hypercubes,$Q_2^n$, and circular graphs,Circn. In particular we show that there exists a covering map$\phi: Q_2^n\to K_{n+1}$if and only if2n≡0modn+1. Furthermore, we provide an interpretation of a class of invertible SDSs over circle graphs as right-shifts of lengthn-2over{0,1}2n-2. The paper concludes with a brief discussion of how we can extend a given covering map to a covering map over certain extended graphs.