2024/09/12 by Bridoux, Florian, Marchetto, Aymeric Picard, Richard, Adrien
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.08041
An automata network with n components over a finite alphabet Q of size q is a discrete dynamical system described by the successive iterations of a function f:Qn→ Qn. In most applications, the main parameter is the interaction graph of f: the digraph with vertex set [n] that contains an arc from j to i if fi depends on input j. What can be said on the set \mathbbG(f) of the interaction graphs of the automata networks isomorphic to f? It seems that this simple question has never been studied. In a previous paper, we prove that the complete digraph Kn, with n2 arcs, is universal in that Kn∈ \mathbbG(f) whenever f is not constant nor the identity (and n≥ 5). In this paper, taking the opposite direction, we prove that there exist universal automata networks f, in that \mathbbG(f) contains all the digraphs on [n], excepted the empty one. Actually, we prove that the presence of only three specific digraphs in \mathbbG(f) implies the universality of f, and we prove that this forces the alphabet size q to have at least n prime factors (with multiplicity). However, we prove that for any fixed q≥ 3, there exists almost universal functions, that is, functions f:Qn→ Qn such that the probability that a random digraph belongs to \mathbbG(f) tends to 1 as n→∞. We do not know if this holds in the binary case q=2, providing only partial results.