2015/03/16 by Gadouleau, Maximilien, Richard, Adrien
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1503.04688
Does the interaction graph of a finite dynamical system can 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:An→ An 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:An→ An with G as interaction graph that converges toward a unique fixed point in at most \lfloorlog2 n\rfloor+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.