Isomorphic Boolean networks and dense interaction graphs

Abstract

A Boolean network (BN) with $n$ components is a discrete dynamical system described by the successive iterations of a function $f:\{0,1{\}}^n\to \{0,1{\}}^n$. In most applications, the main parameter is the interaction graph of $f$: the digraph with vertex set $\{1,\dots ,n\}$ that contains an arc from $j$ to $i$ if $f_i$ depends on input $j$. What can be said on the set $\mathcal{G}(f)$ of the interaction graphs of the BNs $h$ isomorphic to $f$, that is, such that $h\circ \pi =\pi \circ f$ for some permutation $\pi$ of $\{0,1{\}}^n$? It seems that this simple question has never been studied. Here, we report some basic facts. First, if $n\ge 5$ and $f$ is neither the identity or constant, then $\mathcal{G}(f)$ is of size at least two and contains the complete digraph on $n$ vertices, with $n^2$ arcs. Second, for any $n\ge 1$, there are $n$-component BNs $f$ such that every digraph in $\mathcal{G}(f)$ has at least $n^2/9$ arcs.

13 pages