REDUCTION OF DISCRETE DYNAMICAL SYSTEMS OVER GRAPHS
Authors:
- 1 March 2004
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Advances in Complex Systems
- Vol. 07 (01) , 1-20
Abstract
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 graph Y with vertex set {1,2,…,n} where each vertex has associated a binary state, (ii) a collection of Y-local functions (Fi,Y)i∈ v [Y] with [Formula: see text] and (iii) a permutation π of the vertices of Y. The SDS induced by (i)–(iii) is the map [Formula: see text] 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, [Formula: see text], and circular graphs, Circ n. In particular we show that there exists a covering map [Formula: see text] if and only if 2n≡0 mod n+1. Furthermore, we provide an interpretation of a class of invertible SDSs over circle graphs as right-shifts of length n-2 over {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.Keywords
This publication has 7 references indexed in Scilit:
- Swarms of particle agents with harmonic interactionsTheory in Biosciences, 2001
- On Acyclic Orientations and Sequential Dynamical SystemsAdvances in Applied Mathematics, 2001
- Equivalence Relations on Finite Dynamical SystemsAdvances in Applied Mathematics, 2001
- Discrete, sequential dynamical systemsDiscrete Mathematics, 2001
- Acyclic Orientations of Random GraphsAdvances in Applied Mathematics, 1998
- One-Dimensional Dynamics1993
- Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields1983