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