On Acyclic Orientations and Sequential Dynamical Systems

✍ Scribed by C.M. Reidys

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 137 KB
• Volume: 27
• Category: Article
• ISSN: 0196-8858
• DOI: 10.1006/aama.2001.0761

✦ Synopsis

We study a class of discrete dynamical systems that consists of the following data: (a) a finite (labeled) graph Y with vertex set 1 n , where each vertex has a binary state, (b) a vertex labeled multi-set of functions F i Y n 2 → n 2 i , and (c) a permutation π ∈ S n . The function F i Y updates the binary state of vertex i as a function of the states of vertex i and its Y -neighbors and leaves the states of all other vertices fixed. The permutation π represents a Y -vertex ordering according to which the functions F i Y are applied. By composing the functions F i Y in the order given by π we obtain the sequential dynamical system (SDS):

In this paper we first establish a sharp, combinatorial upper bound on the number of non-equivalent SDSs for fixed graph Y and multi-set of functions F i Y . Second, we analyze the structure of a certain class of fixed-point-free SDSs.