Simple dynamics on graphs

Can the interaction graph of a finite dynamical system force this system to have a “complex” dynamics? In other words, given a finite interval of integers A, which are the signed digraphs G such that every finite dynamical system f: A n → A n with G as interaction graph has a “complex” dynamics? If | A | ≥ 3 we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph G there exists a system f: A n → A n with G as interaction graph that converges toward a unique fixed point in at most ⌊ log 2 ⁡ n ⌋ + 2 steps. The boolean case | A | = 2 is more difficult, and we provide partial answers instead. We exhibit large classes of unsigned digraphs which admit boolean dynamical systems which converge toward a unique fixed point in polynomial, linear or constant time.

Authors

• Maximilien Gadouleau
• Adrien Richard

Keywords

• Discrete dynamical system
• Boolean network
• Interaction graph
• Fixed point