Simple dynamics on graphs (Q266275): Difference between revisions

Let \(f\) be a \textit{finite dynamical system}, that is, a function \(f:A^n\rightarrow A^n\), \(x=(x_1,\ldots,x_n) \mapsto f(x)=(f_1(x),\ldots,f_n(x))\), where \(A=\{0,\ldots,s-1\}\). Such a finite dynamical system is more succinctly called a \textit{function over \(A\)}. Its \textit{interaction digraph} has vertex set \(\{1,\ldots,n\}\) and an arc from \(j\) to \(i\) if \(f_i\) depends on \(x_j\). The arc may be labelled indicating whether \(f_i(x)\) is an increasing function of \(x_j\), decreasing function of \(x_j\) or neither. In this case we say that the interaction graph is \textit{signed}. If \(f\) has (signed or unsigned) interaction digraph \(D\), then \(D\) is said to admit \(f\). In applications, one may possess considerable information about the interaction digraph, but know little about \(f\). This paper considers what one may deduce about \(f\) given its (signed or unsigned) interaction digraph, in particular, given a (signed or unsigned) digraph \(D\) and the value of \(s\), does \(D\) admit a function \(f\) over \(A\) such that \(f^k\) is constant? Such a function is called \textit{nilpotent} and the smallest value of \(k\) is called the \textit{class} of \(f\). The authors show that if \(s\geq 4\), then every signed digraph \(D\), admits a function over \(A\) of class at most 2 and a similar result holds when \(s=3\), except that now the class may be as large as \(\lfloor \log n \rfloor +2\). The Boolean case, that is when \(s=2\), is more complicated. Indeed, there are signed digraphs that do not admit a function over \(\{0,1\}\). To simplify matters, the authors consider only unsigned digraphs and give two different sufficient conditions for a strong digraph to admit a nilpotent Boolean function, one case leading to a constant upper bound on the class and the other not. In the special case where \(D\) is symmetric, that is the arc \((i,j)\) is present if and only if the arc \((j,i)\) is present, the authors show that \(D\) admits a Boolean nilpotent function of class 3, providing \(D\) is connected and not \(K_2\).