A Boolean network maps Boolean configurations of fixed length to themselves. A trapspace is an invariant subcube; a principal trapspace is the smallest trapspace containing a configuration, while a minimal trapspace contains no proper trapspace. Commutative Boolean networks are those whose local updates commute. We connect these concepts through five contributions. First, we introduce trapping graphs and trapping closures, define trapping networks by transitivity of their general asynchronous graphs, and prove that they are exactly the trapping closures. Second, we show that two Boolean networks have the same collections of principal trapspaces if and only if they have the same trapping closure. Hence, trapping networks provide a normal form for trapspace analysis. We also characterize the possible collections of principal and minimal trapspaces. Third, we prove that commutative networks are trapping and classify their principal trapspaces. Fourth, we study bijective commutative networks, called Marseille networks, and give equivalent characterizations and classifications. Fifth, we study idempotent commutative networks, called Lille networks, relate them to globally idempotent networks, prove that globally idempotent networks are trapping, and provide equivalent characterizations. These results clarify the relationships among asynchronous, general asynchronous, and trapping graphs and describe the structure of trapping networks.
Boolean networks are a fundamental framework for addressing complex systems, with prominent applications in biology, ecology, and social sciences [11, 13, 16, 18, 22]. A Boolean network represents a network of \(n\) interacting entities, where each entity \(i \in [n]\) has a Boolean state \(x_i \in \mathbb{B}\), which evolves over time according to a deterministic function \(f_i(x_1, \dots, x_n)\) of the current states of the entities. Mathematically, a Boolean network is simply a mapping \(f : \mathbb{B}^n \to \mathbb{B}^n\), which takes an overall configuration of states \(x = (x_1, \dots, x_n)\) as input and returns \(f(x) = (f_1(x), \dots, f_n(x))\). Applying \(f\) to \(x\) corresponds to all entities updating their state at the same time, which is referred to as the parallel schedule.
Of course, different entities may update their state according to different schedules, yielding (general) asynchronous updates. Since the original works by Kauffman [14] and Thomas [23], asynchronous updates have been widely studied, both in terms of modelling purposes and of dynamical analysis (see [5, 6] and references therein). The update of a subset \(S \subseteq [n]\) of entities can be represented by \(f^{(S)}\), where \(f^{(S)}( x ) = (f_S(x), x_{-S})\), and updating \(S\) and \(T\) successively can be represented by \(f^{(S, T)} = f^{(T)} \circ f^{(S)}\). In the fully asynchronous case, only updates of the form \(f^{(i)}\) for some \(i \in [n]\) occur. All the general asynchronous transitions of the form \(x \to f^{(S)}(x)\) are collected in the general asynchronous graph of \(f\), while the asynchronous graph of \(f\) only considers asynchronous transitions of the form \(x \to f^{(i)}(x)\).
Arguably the most well studied property of Boolean networks is their fixed points, i.e. \(x\) such that \(f(x) = x\) (see [3, 4, 10, 20] and references therein). Beyond their intrinsic significance as “stable states” of the modelled network, fixed points have an important theoretical property: they are immune to changes in the update schedule. Indeed, if \(x\) is a fixed point, then \(x\) is also a fixed point of \(f^{(S)}\) for any \(S \subseteq [n]\).
A trapspace of a Boolean network can be viewed as a “localised” fixed point, where only part of the network is fixed. More formally, a trapspace is an invariant subcube: it is a set of the form \(X = \{ x \in \mathbb{B}^n : x_S = 0, x_T = 1 \}\) obtained by fixing some states which satisfies \(f(X) \subseteq X\), so that those states remain fixed [15]. Trapspaces have garnered a lot of interest due to their significance in biological applications. Moreover, like fixed points, they are also immune to changes in the update schedule, which makes them theoretically important.
A trapspace is minimal if it does not contain any smaller trapspace. Minimal trapspaces of networks have been notably studied for their relation with limit (ultimately periodic) configurations: each minimal trapspace necessarily contains at least one limit configuration [15, 17].
Many different classes of Boolean networks have been proposed, based on their interaction graphs (e.g. [1, 21]), the nature of their local functions (e.g. [4, 12]), their metric properties (e.g. [9, 19]) etc. Recently, Bridoux et al. [7] introduced the class of commutative networks, where the updates \(f^{(S)}\) and \(f^{(T)}\) commute for all \(S, T \subseteq [n]\). Remarkably, commutative networks are extremely well structured, and their asynchronous graphs have been fully classified. A review of some of the main results in [7] will be provided in Section 5.1.
The main scope of this paper brings together the study of trapspaces of networks and that of commutative networks. The contributions of this paper are broad, as they cover trapping networks, collections of trapspaces, commutative networks, bijective commutative networks, and idempotent commutative networks. Let us give an overview of each contribution.
Section 3 is devoted to so-called trapping networks. We first introduce the trapping graph, which only depends on the principal trapspaces of the network. The trapping graph has a handy representation as the general asynchronous graph of another network, which we refer to as the trapping closure. We then introduce trapping networks as the networks with transitive general asynchronous graphs; a network is trapping if it is the trapping closure of some other network. Our first main result, Theorem 3.4, gives seven different definitions of trapping networks, including the two provided in Table 1.
| \(\forall x \in \mathbb{B}^n, y \in [x, f(x)]\) | \(\forall S, T \subseteq [n]\) | |
|---|---|---|
| Trapping | \(\textcolor{magenta}{[y, f(y)]} \subseteq [x, f(x)]\) | \(\textcolor{magenta}{f^{(S,T)}} \sqsubseteq f^{(S \cup T)}\) |
| Commutative | \([y, f(x)] \subseteq \textcolor{blue}{[y, f(y)]} \subseteq [x, f(x)]\) | \(f^{(S \Delta T)} \sqsubseteq \textcolor{blue}{f^{(S,T)}} \sqsubseteq f^{(S \cup T)}\) |
| Marseille | \(\textcolor{cyan}{[y, f(y)]} = [x, f(x)]\) | \(\textcolor{cyan}{f^{(S,T)}} = f^{(S \Delta T)}\) |
| Lille | \(\textcolor{red}{[y, f(y)]} = [y, f(x)]\) | \(\textcolor{red}{f^{(S,T)}} = f^{(S \cup T)}\) |
| Globally Idempotent | \(\textcolor{orange}{[y, f(y)]} \subseteq [y, f(x)]\) | \(f^{(S \cap T)} \sqsubseteq \textcolor{orange}{f^{(S,T)}}\) |
Section 4 is devoted to collections of (principal) trapspaces of Boolean networks. We first prove in Theorem 4.1 that the following are equivalent for two networks: they have the same collection of trapspaces, they have the same collection of principal trapspaces, they have the same trapping graph / closure. As such, the trapping closure is a “normal form” when studying trapspaces: it is the network with the most transitions amongst those with the same collection of trapspaces. In turn, this shows that when studying trapspaces, one can restrict oneself to trapping networks. We then give in Theorem 4.3 a full classification of the collections of (principal) trapspaces of Boolean networks, and how they relate to one another and to trapping networks. We finally give a full characterisation of the collections of minimal trapspaces of Boolean networks, and show that two networks with the same collection of minimal trapspaces can have different trapspaces.
Section 5 is denoted to commutative networks. Firstly, in Theorem 5.2, we prove that commutative networks are trapping and we provide the alternate definitions of commutative networks in Table 1. Secondly, in Theorem 5.3, we classify the collections of principal trapspaces of commutative networks.
Section 6 is devoted to bijective commutative networks, which we refer to as Marseille networks1. We make three main contributions with regards to Marseille networks.
Firstly, we give four alternate definitions of Marseille networks, including those in Table 1, in Theorem 6.1.
Secondly, we study the properties of networks with symmetric asynchronous / general asynchronous / trapping graphs and relate them to involutive networks in Theorem 6.2. In particular, the following are equivalent for a network: it is Marseille; it is globally involutive (i.e. \(f^{(S,S)} = \mathrm{id}\) for all \(S \subseteq [n]\)); its general asynchronous graph is symmetric.
Thirdly, we characterise Marseille networks as particular trapping or commutative networks in Theorem 6.4. In particular, all locally bijective (i.e. \(f^{(i)}\) is a bijection for all \(i \in [n]\)) trapping networks are Marseille.
Section 7 is devoted to idempotent commutative networks, which we refer to as Lille networks. We make four main contributions with regards to Lille networks.
Firstly, we give four alternate definitions of Lille networks, including those in Table 1, in Theorem 7.1.
Secondly, we study the properties of networks with triangular (i.e. acyclic with loops) or oriented asynchronous / general asynchronous / trapping graphs and relate them to idempotent networks in Theorem 7.3. In particular, a trapping network is fixable (i.e. its asynchronous attractors are fixed points) if and only if every trapspace contains a fixed point.
Thirdly, we consider the fifth main class of networks in this paper, namely globally idempotent networks. Lille networks are exactly the commutative globally idempotent networks. In Theorem 7.4, we prove that globally idempotent networks are trapping and we provide the alternate definitions of globally idempotent networks in Table 1.
Fourthly, we characterise Lille networks as particular trapping or commutative networks in Theorem 7.5. In particular, a network is fixable if for any configuration \(x\), there is a path in the asynchronous graph from \(x\) to a fixed point. We show that Lille networks are exactly the fixable commutative networks.
We denote the Boolean set by \(\mathbb{B}= \{0,1\}\) and for any positive integer \(n\), we denote \([n] = \{1, \dots, n \}\). A configuration is \(x = (x_1, \dots, x_n) \in \mathbb{B}^n\). For any \(S \subseteq [n]\), we denote \(x_S = (x_s : s \in S)\) and \(x_{-S} = ( x_t : t \notin S )\), and we use the notation \(x = (x_S, x_{-S})\). We shall identify an element \(i \in [n]\) with the corresponding singleton \(\{ i \}\), so that \(x = (x_i, x_{-i})\) for instance. For any two configurations \(x, y \in \mathbb{B}^n\), we denote the set of positions where they differ by \(\Delta( x, y ) = \{ i \in [n] : x_i \ne y_i \}\) and their Hamming distance by \(d_\mathrm{H}( x, y ) = | \Delta(x, y) |\). For any Boolean variable \(a \in \mathbb{B}\), we denote its negation by \(\neg a = 1 – a\); we extend this notation to configurations of any length by componentwise negation: \(\neg x = ( \neg x_1, \dots, \neg x_n )\).
A subcube of \(\mathbb{B}^n\) is any \(X \subseteq \mathbb{B}^n\) such that there exist two disjoint sets of positions \(S, T \subseteq [n]\) with \(X = \{ x \in \mathbb{B}^n : x_S = 0, x_T = 1 \}\). For any set \(A \subseteq \mathbb{B}^n\), the principal subcube of \(A\), denoted by \([A]\), is the smallest subcube containing \(A\). If \(A = \{a_1, \dots, a_k\}\), we also denote \([A] = [a_1, \dots, a_k]\). If \(X\) is a subcube and \(x \in X\), then there is a unique \(y \in X\) such that \(X = [x, y]\); we refer to \(y\) as the opposite of \(x\) in \(X\), and we denote it by \(y = X – x\). We denote the set of subcubes of \(\mathbb{B}^n\) by \(\mathrm{S} (n)\) and the set of all collections of subcubes of \(\mathbb{B}^n\) by \(\mathrm{A} (n) = 2^{ \mathrm{S} (n) }\).
A Boolean network (or simply, network) of dimension \(n\) is a mapping \(f : \mathbb{B}^n \to \mathbb{B}^n\). We denote the set of networks of dimension \(n\) as \(\mathrm{F} (n)\). For any \(x \in \mathbb{B}^n\), we refer to the subcube \([x, f(x)]\) as the interval of \(x\) with respect to \(f\). Any network \(f \in \mathrm{F} (n)\) can be viewed as \(f = (f_1, \dots, f_n)\) where \(f_i : \mathbb{B}^n \to \mathbb{B}\) is given by \(f_i(x) = f(x)_i\) for all \(i \in [n]\). For any \(S \subseteq [n]\) and any \(f \in \mathrm{F} (n)\), the update of \(S\) according to \(f\) is represented by the network \(f^{(S)} \in \mathrm{F} (n)\) where \[f^{ (S) }( x ) = ( f_S( x ), x_{-S} ).\]
In particular, \(f^{ ([n]) } = f\) and \(f^{ (\emptyset) } = \mathrm{id}\). We note the distinction between the update \(f^{ (i) }\) (given by \(f^{ (i) }(x) = ( f_i( x ), x_{-i} )\)) and the power \(f^i = f \circ f \circ \dots \circ f\) (\(i\) terms). We can then compose those updates, so that if \(S_1, \dots, S_k \subseteq [n]\), we obtain \[f^{( S_1, \dots, S_k )} = f^{(S_k)} \circ f^{(S_{k-1})} \circ \dots \circ f^{(S_1)}.\]
A (directed) graph is \(\Gamma = (V, E)\), where \(V\) is the set of vertices and \(E \subseteq V^2\) is the set of edges. A graph \(\Gamma\) is reflexive if for all \(v \in V\), \((v,v) \in E\); \(\Gamma\) is symmetric if \((u,v) \in E\) implies \((v,u) \in E\) for all \(u,v \in V\); and \(\Gamma\) is transitive if \((u,v), (v,w) \in E\) implies \((u,w) \in E\) for all \(u,v,w \in V\). The out-neighbourhood of a vertex \(v\) is \(N^{out}( \Gamma ; v) = \{ u \in V : (v,u) \in E \}\).
The asynchronous graph of a network \(f \in \mathrm{F} (n)\) is the graph \(\mathtt{A} (f) = (V, E)\) where \(V = \mathbb{B}^n\) and \[E = \{ (x, f^{ (i) }(x) ) : x \in \mathbb{B}^n, i \in [n] \}.\]
We remark that a Boolean network is fully characterised by its asynchronous graph. Note that in most literature, one removes the loops \((x, x)\) from the asynchronous graph, that occur every time \(f_i(x) = x_i\), yet we shall keep those loops instead in our definition. However, when drawing the asynchronous graph, we shall not display the loops and instead draw the underlying hypercube with thin black lines and the arcs of the graph with thick blue arrows. See below for an example of a network, for which we give the asynchronous graph.
Example 2.1. Consider the Boolean network \(f \in \mathrm{F} ( 3 )\).
| \(x\) | \(f(x)\) |
|---|---|
| \(000\) | \(110\) |
| \(001\) | \(100\) |
| \(010\) | \(000\) |
| \(011\) | \(110\) |
| \(100\) | \(100\) |
| \(101\) | \(101\) |
| \(110\) | \(110\) |
| \(111\) | \(110\) |
The asynchronous graph of \(f\) is given as follows.
The general asynchronous graph of a network \(f \in \mathrm{F} (n)\) is the graph \(\mathtt{GA} (f) = (V, E)\) where \(V = \mathbb{B}^n\) and \[E = \{ (x, f^{ (S) }(x) ) : x \in \mathbb{B}^n, S \subseteq [n] \}.\]
Equivalently, the out-neighbourhood of a configuration in the general asynchronous graph is given by its interval: \(N^{out}( \mathtt{GA} (f); x) = [x, f(x)]\) for all \(x \in \mathbb{B}^n\). It is clear that the mapping \(\mathtt{GA} : f \mapsto \mathtt{GA} (f)\) is injective. We first characterise the general asynchronous graphs.
Proposition 2.2. Let \(\Gamma\) be a graph on \(\mathbb{B}^n\). Then \(\Gamma = \mathtt{GA} (f)\) for some \(f \in \mathrm{F} (n)\) if and only if \(\Gamma\) is reflexive and all out-neighbourhoods are subcubes.
Proof. We have \(N^{out}( \mathtt{GA} (f); x) = [x, f(x)]\) for all \(x\), i.e. \(\mathtt{GA} (f)\) is reflexive and all out-neighbourhoods are subcubes. Conversely, if \(\Gamma\) is reflexive and all out-neighbourhoods are subcubes, then \(\Gamma = \mathtt{GA} (f)\), where \(f(x) = N^{out}( \Gamma; x ) – x\) for all \(x\). \(\square\)
Example 2.3. Let \(f \in \mathrm{F} (3)\) be the network in Example 2.1. The general asynchronous graph of \(f\) is given as follows. The blue arrows come from \(\mathtt{A} (f)\) while the magenta arrows are additional transitions in \(\mathtt{GA} (f)\); once again we omit the loops on all the vertices.
The networks in \(\mathrm{F} ( n )\) have a natural partial order in terms of their transitions. For any two graphs \(\Gamma_1 = (V, E_1)\), \(\Gamma_2 = (V, E_2)\) on the same vertex \(V\), we write \(\Gamma_1 \subseteq \Gamma_2\) as a shorthand for \(E_1 \subseteq E_2\).
Consider the relation \(f \sqsubseteq g\) on \(\mathrm{F} (n)\) given by the four equivalent conditions:
\(\Delta(x, f(x)) \subseteq \Delta(x, g(x))\) for all \(x \in \mathbb{B}^n\);
\([ x, f(x) ] \subseteq [ x, g(x) ]\) for all \(x \in \mathbb{B}^n\);
\(\mathtt{GA} (f) \subseteq \mathtt{GA} (g)\);
\(\mathtt{A} ( f ) \subseteq \mathtt{A} ( g )\).
The \(\sqsubseteq\) partial order induces a lattice \(\mathcal{F} _n = ( \mathrm{F} (n), \sqcup, \sqcap, \mathbf{0} , \mathbf{1} )\) (a Boolean algebra isomorphic to \(2^E\), where \(E = \{ (u,v) : u,v \in \mathbb{B}^n, d_\mathrm{H}(u,v) = 1 \}\) is the set of arcs of the hypercube) with \[\begin{aligned} \mathtt{GA} ( f \sqcup g ) &= \mathtt{GA} (f) \cup \mathtt{GA} (g)\\ \mathtt{GA} ( f \sqcap g ) &= \mathtt{GA} (f) \cap \mathtt{GA} (g)\\ \mathbf{0} &= \mathrm{id} \quad (\text{the identity network: } f(x) = x)\\ \mathbf{1} &= \neg \quad (\text{the negation network: } f(x) = \neg x). \end{aligned}\]
We note that the ordering behaves well when considering updates of subsets: \(f^{(S)} \sqsubseteq f^{(S \cup T)}\) for all \(S, T \subseteq [n]\) and \(f \sqsubseteq g \implies f^{(S)} \sqsubseteq g^{(S)}\) for all \(S \subseteq [n]\).
A trapspace of \(f \in \mathrm{F} (n)\) is a subcube \(X \subseteq \mathbb{B}^n\) that satisfies the following three equivalent conditions [15]:
\(f(X) \subseteq X\);
\(f^{(i)}( X ) \subseteq X\) for all \(i \in [n]\);
\(f^{(S)}( X ) \subseteq X\) for all \(S \subseteq [n]\).
The collection of all trapspaces of \(f\), denoted by \(\mathcal{T} (f)\), is closed under intersection. Then for any \(x \in \mathbb{B}^n\), there is a smallest trapspace of \(f\) that contains \(x\), which we shall refer to as the principal trapspace of \(x\) (with respect to \(f\)). For the sake of simplicity, we denote it by \(T_f(x)\). The principal trapspace \(T_f(x)\) can be recursively computed as follows: let \(T_0 = \{ x \}\) and \(T_i = [T_{i-1} \cup f( T_{i-1} )]\), then \(T_n = T_f(x)\). In particular, the principal trapspace of \(x\) contains the interval of \(x\): \([x, f(x)] \subseteq T_f(x)\). The collection of all principal trapspaces of \(f\) is denoted by \(\mathcal{P} (f)\). A trapspace \(T\) is minimal if there is no trapspace \(T’\) with \(T’ \subset T\). Clearly, any minimal trapspace is principal, but the converse does not necessarily hold. The collection of minimal trapspaces of \(f\) is denoted by \(\mathcal{M} (f)\).
Example 2.4. Let \(f \in \mathrm{F} (3)\) be the network from Examples 2.1 and 2.3. The principal trapspaces of \(f\) are given as follows: \[\begin{aligned} T_f(000) &= [000,110] = \{ x : x_3 = 0 \} \\ T_f(001) &= [001,110] = \{ x \} \\ T_f(010) &= [010,100] = \{ x : x_3 = 0 \} \\ T_f(011) &= [011,100] = \{ x \} \\ T_f(100) &= [100,100] = \{ x : x_1 = 1, x_{23} = 00 \} \\ T_f(101) &= [101,101] = \{ x : x_{13} = 11, x_2 = 0 \} \\ T_f(110) &= [110,110] = \{ x : x_{12} = 11, x_3 = 0 \} \\ T_f(111) &= [111,110] = \{ x : x_{12} = 11 \}. \end{aligned}\]
It has three other trapspaces, namely \(\{ x : x_1 = 1, x_2 = 0 \}\), \(\{ x : x_1 = 1, x_3 = 0 \}\), and \(\{ x : x_1 = 1 \}\).
The trapping graph of a network \(f \in \mathrm{F} (n)\) is the graph \(\mathtt{T} (f) = (V, E)\) where \(V = \mathbb{B}^n\) and \[E = \{ (x,y) : x \in \mathbb{B}^n, y \in T_f( x ) \}.\]
If \(y \in T_f(x)\), then \(T_f(x)\) is a trapspace of \(f\) containing \(y\), thus \(T_f(y) \subseteq T_f(x)\); in other words, the trapping graph is transitive. In \(\mathtt{T} (f)\), the out-neighbourhood of \(x\) is a subcube containing \(x\); therefore, the trapping graph of \(f\) is the general asynchronous graph of another network. More concretely, let \({f}^\mathrm{T} \in \mathrm{F} (n)\) be the network that maps \(x\) to its opposite in that subcube, i.e. \[{f}^\mathrm{T} (x) = T_f(x) – x,\] so that \(T_f(x) = [x, {f}^\mathrm{T} (x)]\) and \(\mathtt{GA} ( {f}^\mathrm{T} ) = \mathtt{T} ( f )\). We refer to \({f}^\mathrm{T}\) as the trapping closure of \(f\).
Example 3.1. Let \(f \in \mathrm{F} (3)\) be the network from Examples 2.1, 2.3 and 2.4. The trapping graph of \(f\) is given as follows. The blue arrows come from \(\mathtt{A} (f)\), the magenta arrows are additional transitions in \(\mathtt{GA} (f)\), while the orange arrows are additional transitions in \(\mathtt{T} (f)\); once again we omit the loops on all the vertices.
The asynchronous graph of \({f}^\mathrm{T}\) is given as follows, where the blue arrows come from \(\mathtt{A} (f)\), while the additional transitions in \(\mathtt{A} ( {f}^\mathrm{T} )\) are highlighted in violet.
Proposition 3.2. The operator \(f \mapsto {f}^\mathrm{T}\) is a closure operator on the lattice \(\mathcal{F} _n\): for all \(f, g \in \mathrm{F} (n)\) we have
Proof. Eq. (1). Since \(f(x) \in T_f(x)\) for all \(x\), we obtain \(f \sqsubseteq {f}^\mathrm{T}\).
Eq. (2). Suppose \(f \sqsubseteq g\), then we need to prove that \(T_f(x) \subseteq T_g(x)\) for all \(x \in \mathbb{B}^n\). For all \(y \in T_g(x)\), we have \([y, g(y)] \subseteq T_g(x)\) hence \([y, f(y)] \subseteq T_g(x)\). Thus \(T_g(x)\) is a trapspace of \(f\) containing \(x\) whence \(T_f(x) \subseteq T_g(x)\).
Eq. (3). Let \(g = {f}^\mathrm{T}\). We prove that \(T_g(x) = T_f(x)\) for all \(x \in \mathbb{B}^n\). Firstly, \(T_f(x) \subseteq T_g(x)\) because \(f \sqsubseteq g\). Conversely, for any \(y \in T_f(x)\), we have \(T_f(y) = [y, g(y)] \subseteq T_f(x)\), hence \(g(y) \in T_f(x)\). Therefore \(T_f(x)\) is a trapspace of \(g\) containing \(x\), thus \(T_g(x) \subseteq T_f(x)\). \(\square\)
We can now give an algebraic characterisation of \({f}^\mathrm{T}\).
Corollary 3.3. For all \(f \in \mathrm{F} (n)\) we have \[{f}^\mathrm{T} = {\sqcap} \{ {g}^\mathrm{T} : f \sqsubseteq g\}.\]
Proof. Immediately follows from [8, Theorem 1.1] applied to \(\mathcal{F} _n\). \(\square\)
We say a network is trapping if its general asynchronous graph is transitive. Denote the set of all trapping networks in \(\mathrm{F} (n)\) by \({ \mathrm{F} }^\mathrm{T} (n)\). We now provide a list of equivalent definitions of trapping networks.
Many proofs of our results will be broken down into smaller proofs of the form “Property \(A\) \(\implies\) Property \(B\)”. For all such proofs, we omit the introductory sentence: “Let \(f \in \mathrm{F} ( n )\) satisfy \(A\).”
Theorem 3.4 (Alternate definitions of trapping networks). For all \(f \in \mathrm{F} (n)\), the following are equivalent:
(a) \(f\) is trapping, i.e. \(\mathtt{GA} ( f )\) is transitive,
(b) \([ y, f(y) ] \subseteq [ x, f(x) ]\) for all \(x \in \mathbb{B}^n\) and \(y \in [x, f(x) ]\),
(c) \([x, f(x)] = T_f( x )\) for all \(x \in \mathbb{B}^n\),
(d) \(f = {f}^\mathrm{T}\),
(e) \(f = {g}^\mathrm{T}\) for some \(g \in \mathrm{F} ( n )\),
(f) \(\mathtt{T} ( f ) = \mathtt{GA} ( f )\).
(g) \(f^{(S,T)} \sqsubseteq f^{(S \cup T)}\) for all \(S, T \subseteq [n]\).
Proof. (a)\(\iff\) (b). By definition.
(b)\(\implies\)(c). If \(f(y) \in [x, f(x)]\) for all \(y \in [x, f(x)]\), then \([x, f(x)]\) is a trapspace. Since \(T_f( x )\) is the smallest trapspace that contains \(x\), and \([x, f(x)] \subseteq T_f( x )\), we obtain \([x, f(x)] = T_f( x )\).
(c) \(\implies\)(b). If \([x, f(x)]\) is a trapspace, then \(f(y) \in [x, f(x)]\) for all \(y \in [x, f(x)]\).
(c)\(\iff\)(d). By definition.
(d)\(\implies\)(e). Trivial.
(e)\(\implies\)(d). Follows directly from (3) in Proposition 3.2.
(d)\(\implies\)(f). If \(f = {f}^\mathrm{T}\), then \(\mathtt{GA} ( f ) = \mathtt{GA} ( {f}^\mathrm{T} ) = \mathtt{T} ( f )\).
(f)\(\implies\)(a). If \(\mathtt{GA} ( f ) = \mathtt{T} ( f )\), then \(\mathtt{GA} ( f )\) is indeed transitive.
(c)\(\implies\)(g). Suppose \(x \to z\) in \(\mathtt{GA} ( f^{(S,T)} )\). Denoting \(s = f^{(S)}( x )\) and \(t = f^{(T)}(s)\), we have \(s \in [x, f(x)] = T_f( x )\), \(t \in T_f( s ) \subseteq T_f( x )\), and \(z \in [x, t] \subseteq T_f( x ) = N^{out}( \mathtt{GA} (f) ; x )\). Since \(\Delta( x, z ) \subseteq \Delta(x, t) \subseteq S \cup T\), we obtain \(z \in N^{out}( \mathtt{GA} ( f^{(S \cup T)} ) ; x )\). Thus, \(f^{( S,T )} \sqsubseteq f^{( S \cup T )}\).
(g)\(\implies\)(a). Let \(x \to y \to z\) in \(\mathtt{GA} ( f )\), so that \(y = f^{(S)}( x )\) and \(z = f^{(T)} (y) = f^{(S, T)} (x)\) for some \(S, T \subseteq [n]\). We obtain \(x \to z\) in \(\mathtt{GA} ( f^{(S,T)} ) \subseteq \mathtt{GA} ( f^{(S \cup T)} ) \subseteq \mathtt{GA} ( f )\). Therefore, \(\mathtt{GA} ( f )\) is transitive. \(\square\)
Theorem 3.4 yields the following corollary.
Corollary 3.5. For all \(f \in \mathrm{F} (n)\), \[\mathtt{T} (f) = \mathtt{GA} ( {f}^\mathrm{T} ) = \mathtt{T} ( {f}^\mathrm{T} ).\]
We can also classify the trapping graphs as the transitive general asynchronous graphs.
Corollary 3.6. Let \(\Gamma\) be a graph on \(\mathbb{B}^n\). Then \(\Gamma = \mathtt{T} (f)\) for some \(f \in \mathrm{F} (n)\) if and only if \(\Gamma\) is reflexive transitive and all out-neighbourhoods are subcubes.
Proof. By Proposition 2.2, \(\Gamma\) is reflexive transitive and all out-neighbourhoods are subcubes if and only if it is a transitive general asynchronous graph, i.e. \(\Gamma = \mathtt{GA} (g)\) for some trapping network \(g\). By Corollary 3.5, this is equivalent to \(\Gamma = \mathtt{T} (f)\) for some network \(f\). \(\square\)
Trapping graphs form a rich class of graphs. For instance, any \(X \subseteq \mathbb{B}^n\) can appear as an initial strong component of some trapping graph (namely, for \(f(x) = \neg x\) if \(x \in X\) and \(f(x) = x\) otherwise). Note, however, that if \(\mathtt{T} (f)\) has two distinct strong components \(S, T\) with \(S \to T\), then \([T] \subset [S]\).
We begin this section with a characterisation of networks that have the same collection of trapspaces. In particular, Theorem 4.1 below shows that trapping networks are a canonical form for networks when studying their trapspaces. Recall that the collection of all trapspaces of \(f\) is denoted by \(\mathcal{T} (f)\), while the collection of all principal trapspaces of \(f\) is denoted by \(\mathcal{P} (f)\).
Theorem 4.1 (Trapspace equivalent networks). Let \(f, g \in \mathrm{F} (n)\). The following are equivalent:
(a) \(f\) and \(g\) have the same collection of principal trapspaces, i.e. \(\mathcal{P} (f) = \mathcal{P} (g)\);
(b) \(f\) and \(g\) have the same collection of trapspaces, i.e. \(\mathcal{T} (f) = \mathcal{T} (g)\);
(c) \(f\) and \(g\) have the same principal trapspaces pointwise, i.e. \(T_f(x) = T_g(x)\) for all \(x \in \mathbb{B}^n\);
(d) \(f\) and \(g\) have the same trapping graph, i.e. \(\mathtt{T} (f) = \mathtt{T} (g)\);
(e) \(f\) and \(g\) have the same trapping closure, i.e. \({f}^\mathrm{T} = {g}^\mathrm{T}\).
Proof. (a)\(\implies\)(c). Let \(x \in \mathbb{B}^n\). On the one hand, since \(T_f(x)\) and \(T_g(x)\) are trapspaces of \(f\) containing \(x\), we have \(T_f(x) \subseteq T_g(x)\). We similarly obtain \(T_g(x) \subseteq T_f(x)\), and hence \(T_f(x) = T_g(x)\).
(c)\(\implies\)(b). We have \[A \in \mathcal{T} (f) \iff A = \bigcup \{ T_f(x) : x \in A \} \iff A = \bigcup \{ T_g(x) : x \in A \} \iff A \in \mathcal{T} (g).\]
(b)\(\implies\)(a). Trivial.
(c)\(\iff \text{ (d) }\iff\)(e). Immediate from the definitions of \(\mathtt{T} (f)\) and \({f}^\mathrm{T}\). \(\square\)
Corollary 4.2. For any network \(f\), \(\mathcal{P} (f) = \mathcal{P} ( {f}^\mathrm{T} )\) and \(\mathcal{T} ( f ) = \mathcal{T} ( {f}^\mathrm{T} )\).
In this section, we shall classify the collections of trapspaces and the collections of principal trapspaces of networks. We shall moreover illustrate a three-way equivalence amongst collections of principal trapspaces, collections of trapspaces, and trapping closures. This equivalence is similar to the situation for pre-orders on sets.
A pre-order on a set \(\Omega\) is a reflexive transitive binary relation on \(\Omega\). If \(R\) is a pre-order on \(\Omega\), then any set of the form \(S^\downarrow = \{ y \in \Omega : \exists s \in S, (s,y) \in R \}\) for some \(S \subseteq \Omega\) is an ideal of \(R\); a principal ideal of \(R\) is any set of the form \(x^\downarrow = \{ y \in \Omega, (x,y) \in R \}\) for some \(x \in \Omega\). Since \(R = \bigcup_{x \in \Omega, y \in x^\downarrow} (x,y)\), we see that \(R\) can be reconstructed from its collection of principal ideals; the same can be said for its collection of ideals. It is well known that a collection of subsets of \(\Omega\) is the collection of ideals of a pre-order if and only if it is closed under arbitrary unions and intersections; similarly one can classify the collections of principal ideals of pre-orders. Therefore, for the set \(\Omega\), there is a three-way equivalence between a pre-order \(R\) on \(\Omega\), its collection of ideals, and its collection of principal ideals.
In this paper, we are interested in \(\Omega = \mathbb{B}^n\), but we do not consider any possible (principal) ideal. Let \(f \in \mathrm{F} (n)\) be a network. The reachability relation \(R\) given by \(R = \{ (x,y) : x \to_{ \mathtt{GA} (f) } \dots \to_{ \mathtt{GA} (f) } y \}\) is a pre-order on \(\mathbb{B}^n\). A subcube is an ideal of \(R\) if and only if it is a trapspace of \(f\); it is a principal ideal of \(R\) if and only if it is a principal trapspace of \(f\). The relation \(R’\) given by \(y \in T_f(x)\) is also a pre-order, described by the trapping graph (\((x,y) \in R’\) if and only if \((x,y)\) is an edge of \(\mathtt{T} (f)\)). This is the smallest pre-order such that all its principal ideals are principal trapspaces of \(f\). Therefore, the main result is a three-way equivalence between a trapping network, its collection of trapspaces, and its collection of principal trapspaces.
Recall that \(\mathrm{A} (n)\) denotes the set of all collections of subcubes of \(\mathbb{B}^n\). Say a collection \(\mathcal{J} \in \mathrm{A} ( n )\) of subcubes is ideal if it is the collection of trapspaces of a network. We denote the set of all ideal collections of subcubes of \(\mathbb{B}^n\) by \(\mathrm{A} ^ \mathcal{T} (n)\). Accordingly, say a collection \(\mathcal{Q}\) of subcubes is principal if it is the collection of principal trapspaces of a network and denote the set of all principal collections of subcubes of \(\mathbb{B}^n\) by \(\mathrm{A} ^ \mathcal{P} (n)\). We shall give combinatorial descriptions of ideal and principal collections of subcubes in the sequel.
Define the mapping \(F : \mathrm{A} (n) \to \mathrm{F} (n)\) as follows. Let \(\mathcal{A} \in \mathrm{A} (n)\) be a collection of subcubes of \(\mathbb{B}^n\). For any \(x \in \mathbb{B}^n\), denote the intersection of all the subcubes in \(\mathcal{A}\) that contain \(x\) by \[\mathcal{A}(x) := \bigcap \{ A \in \mathcal{A} : x \in A \},\] where \(\mathcal{A}(x) = \mathbb{B}^n\) if the intersection is empty. Then let \(F( \mathcal{A} )\) be the network defined by \[F( \mathcal{A} )(x) = \mathcal{A}(x) – x,\] or equivalently \(\mathcal{A}(x) = [ x, F( \mathcal{A} )(x) ]\), for all \(x \in \mathbb{B}^n\). Let \(F_ \mathcal{P}\) be the restriction of \(F\) to \(\mathrm{A} ^ \mathcal{P} (n)\) and \(F_ \mathcal{T}\) be the restriction of \(F\) to \(\mathrm{A} ^ \mathcal{T} (n)\).
Moreover, define the mappings \(\lambda, \mu : \mathrm{A} ( n ) \to \mathrm{A} ( n )\) given by \[\lambda( \mathcal{A} ) = \left\{ \bigcup R, R \subseteq \mathcal{A} : \bigcup R \in \mathrm{S} ( n ) \right\},\] and \[\mu( \mathcal{A} ) = \{ \mathcal{A}( x ) : x \in \mathbb{B}^n \}.\]
Then let \(\lambda_ \mathcal{P}\) be the restriction of \(\lambda\) to \(\mathrm{A} ^ \mathcal{P} ( n )\) and \(\mu_ \mathcal{T}\) be the restriction of \(\mu\) to \(\mathrm{A} ^ \mathcal{T} ( n )\).
Theorem 4.3 (Three-way equivalence for collections of trapspaces). The diagram on Figure 1 commutes.
More concretely, the following hold.
(a) For all \(\mathcal{Q} \in \mathrm{A} ^ \mathcal{P} (n)\) and all \(g \in { \mathrm{F} }^\mathrm{T} (n)\), we have \[\mathcal{P} ( F_ \mathcal{P} ( \mathcal{Q} ) ) = \mathcal{Q}, \qquad F_ \mathcal{P} ( \mathcal{P} (g) ) = g.\]
(b) For all \(\mathcal{J} \in \mathrm{A} ^ \mathcal{T} (n)\) and all \(g \in { \mathrm{F} }^\mathrm{T} (n)\), we have \[\mathcal{T} ( F_ \mathcal{T} ( \mathcal{J} ) ) = \mathcal{J}, \qquad F_ \mathcal{T} ( \mathcal{T} (g) ) = g.\]
(c) For all \(\mathcal{Q} \in \mathrm{A} ^ \mathcal{P} ( n )\) and all \(\mathcal{J} \in \mathrm{A} ^ \mathcal{T} ( n )\), we have \[\lambda_ \mathcal{P} ( \mathcal{Q} ) = \mathcal{T} ( F_ \mathcal{P} ( \mathcal{Q} ) ), \qquad \mu_ \mathcal{T} ( \mathcal{J} ) = \mathcal{P} ( F_ \mathcal{T} ( \mathcal{J} ) ).\]
(d) For all \(\mathcal{Q} \in \mathrm{A} ^ \mathcal{P} ( n )\) and all \(\mathcal{J} \in \mathrm{A} ^ \mathcal{T} ( n )\), we have \[\mu_ \mathcal{T} ( \lambda_ \mathcal{P} ( \mathcal{Q} ) ) = \mathcal{Q}, \qquad \lambda_ \mathcal{P} ( \mu_ \mathcal{T} ( \mathcal{J} ) ) = \mathcal{J}.\]
The rest of this subsection is devoted to the proof of Theorem 4.3. We first prove item 4.3, by characterising the principal collections of subcubes.
Let \(\mathcal{Q} \in \mathrm{A} (n)\) be a collection of subcubes of \(\mathbb{B}^n\). We say \(\mathcal{Q}\) is pre-principal if \[\mathcal{Q} = \mu( \mathcal{Q} ) = \{ \mathcal{Q}(x) : x \in \mathbb{B}^n \}.\] Intuitively, \(\mathcal{Q}\) is pre-principal if for any configuration \(x\), there exists a smallest subcube in \(\mathcal{Q}\) that contains \(x\), and conversely for any subcube \(A \in \mathcal{Q}\), there is a configuration \(x\) for which \(A\) is the smallest subcube that contains \(x\).
Lemma 4.4. A collection \(\mathcal{Q}\) of subcubes of \(\mathbb{B}^n\) is pre-principal if and only if the following hold:
(a) \(\bigcup \mathcal{Q} = \mathbb{B}^n\);
(b) for all \(A, B \in \mathcal{Q}\), there exists \(\mathcal{C} \subseteq \mathcal{Q}\) such that \(\bigcup \mathcal{C} = A \cap B\);
(c) for all \(A \in \mathcal{Q}\) and \(\mathcal{C} \subseteq \mathcal{Q}\), \(\bigcup \mathcal{C} = A\) implies \(A \in \mathcal{C}\).
Proof. Suppose \(\mathcal{Q}\) is pre-principal. We prove that it satisfies all three properties.
(a) We have \(x \in \mathcal{Q}(x)\) for all \(x \in \mathbb{B}^n\), hence \(\bigcup \mathcal{Q} = \mathbb{B}^n\).
(b) For all \(A, B \in \mathcal{Q}\), \(\bigcup\{ \mathcal{Q}(x) : x \in A \cap B \} = A \cap B\).
(c) Suppose \(\mathcal{C} \subseteq \mathcal{Q}\) with \(\bigcup \mathcal{C} = A \in \mathcal{Q}\) while \(A \notin \mathcal{C}\). Then for all \(x \in A\), there exists \(C \in \mathcal{C}\) such that \(\mathcal{Q}(x) \subseteq C \subset A\). Therefore, \(A \notin \{ \mathcal{Q}(x) : x \in \mathbb{B}^n \}\), which contradicts the fact that \(\mathcal{Q}\) is pre-principal.
Conversely, let \(\mathcal{Q}\) satisfy all three properties. We first prove that \(\mathcal{Q}(x) \in \mathcal{Q}\) for all \(x \in \mathbb{B}^n\). Let \(x \in \mathbb{B}^n\) and consider the collection \[\mathcal{S} = \{ A \in \mathcal{Q} : x \in A; \forall B \subset A, B \in \mathcal{Q}, x \notin B \},\] of minimal subcubes in \(\mathcal{Q}\) that contain \(x\). By Property 4.4, \(|\mathcal{S}| \ge 1\). If \(|\mathcal{S}| \ge 2\), let \(A,B \in \mathcal{S}\), then there exists \(\mathcal{C} \subseteq \mathcal{Q}\) such that \(\bigcup \mathcal{C} = A \cap B\). As such, there exists \(C \in \mathcal{C}\) such that \(x \in C\) while \(C \subseteq A \cap B \subset A\), which contradicts the fact that \(A \in \mathcal{S}\). Therefore, \(|\mathcal{S}| = 1\), hence \(\mathcal{S} = \{ \mathcal{Q}(x) \}\).
We now prove that \(A \in \{ \mathcal{Q}(x) : x \in \mathbb{B}^n \}\) for all \(A \in \mathcal{Q}\). Let \(A \in \mathcal{Q}\), and suppose that \(\mathcal{Q}(x) \subset A\) for all \(x \in A\). Then \(\mathcal{C} := \{ \mathcal{Q}(x) : x \in A \} \subset \mathcal{Q}\) satisfies \(\bigcup \mathcal{C} = A\) while \(A \notin \mathcal{C}\), which contradicts the third property. \(\square\)
Lemma 4.5. A collection of subcubes is principal if and only if it is pre-principal. For all \(\mathcal{Q} \in \mathrm{A} ^ \mathcal{P} (n)\) and all \(g \in { \mathrm{F} }^\mathrm{T} (n)\), we have \[\mathcal{P} ( F_ \mathcal{P} ( \mathcal{Q} ) ) = \mathcal{Q}, \qquad F_ \mathcal{P} ( \mathcal{P} (g) ) = g.\]
Proof. Firstly, we prove that \(F_ \mathcal{P} ( \mathcal{Q} )\) is trapping. Placing ourselves in the graph \(\Gamma = \mathtt{GA} ( F_ \mathcal{P} ( \mathcal{Q} ) )\), if \(y \in N^{out} ( \Gamma; x ) = \mathcal{Q}(x)\), then \(N^{out}( \Gamma; y ) = \mathcal{Q}(y) \subseteq \mathcal{Q}(x) = N^{out}( \Gamma; x )\), and hence \(\Gamma\) is transitive.
Secondly, we prove that \(\mathcal{P} (g)\) is pre-principal by verifying that it satisfies the three properties of Lemma 4.4. First, since \(x \in T_g(x)\) for all \(x \in \mathbb{B}^n\), we have \(\bigcup \mathcal{P} (g) = \mathbb{B}^n\). Second, for all \(A, B \in \mathcal{P} (g)\), the collection \(\mathcal{C} = \{ T_g(x) : x \in A \cap B \}\) satisfies \(\mathcal{C} \subseteq \mathcal{P} (g)\) and \(\bigcup \mathcal{C} = A \cap B\). Third, if there exists \(x \in \mathbb{B}^n\) and \(\mathcal{C} \subseteq \mathcal{P} (g) \setminus \{ T_g(x) \}\) such that \(\bigcup \mathcal{C} = T_g(x)\), then there exists \(C \in \mathcal{C}\) such that \(x \in C \subset T_g(x)\) and hence \(T_g(x) \subseteq C \subset T_g(x)\), which is the desired contradiction.
Since any principal collection of subcubes is of the form \(\mathcal{P} (g)\) for some trapping network \(g\), we have just shown that any principal collection of subcubes is pre-principal.
Thirdly, we prove that \(\mathcal{P} ( F_ \mathcal{P} ( \mathcal{Q} ) ) = \mathcal{Q}\) for any pre-principal collection \(\mathcal{Q}\) of subcubes of \(\mathbb{B}^n\). Let \(g = F( \mathcal{Q} )\). Since \(g\) is trapping, we have for all \(x \in \mathbb{B}^n\) \[T_g(x) = N^{out}( \mathtt{GA} (g); x ) = \mathcal{Q}(x).\]
Hence \(\mathcal{P} (g) = \{ \mathcal{Q}(x) : x \in \mathbb{B}^n \} = \mathcal{Q}\) since \(\mathcal{Q}\) is pre-principal.
We have just shown that any pre-principal collection of subcubes is principal. Together with the previous item, we have proved that a collection of subcubes is principal if and only if it is pre-principal.
Fourthly, we prove that \(F_ \mathcal{P} ( \mathcal{P} (g) ) = g\) for all \(g \in { \mathrm{F} }^\mathrm{T} (n)\). Let \(\mathcal{Q} = \mathcal{P} (g)\). For all \(x \in \mathbb{B}^n\), we have \[T_g(x) = \bigcap\{ A \in \mathcal{P} (g) : x \in A \} = \mathcal{Q}(x).\]
Hence \(\mathcal{Q}(x) = [x, g(x)]\) (since \(g\) is trapping). On the other hand, by definition \(\mathcal{Q}(x) = [ x, F_ \mathcal{P} ( \mathcal{Q} ) (x) ]\), thus \(g = F_ \mathcal{P} ( \mathcal{Q} )\). \(\square\)
We now prove item 4.3, by characterising ideal collections of subcubes. We say that a collection \(\mathcal{J}\) of subcubes is pre-ideal if it satisfies the following three properties:
(a) \(\mathbb{B}^n \in \mathcal{J}\);
(b) \(\mathcal{J}\) is closed under intersection, i.e. if \(A, B \in \mathcal{J}\) and \(A \cap B \ne \emptyset\), then \(A \cap B \in \mathcal{J}\);
(c) for any subcollection \(\mathcal{R} \subseteq \mathcal{J}\), if \(R = \bigcup \mathcal{R} \in \mathrm{S} (n)\), then \(R \in \mathcal{J}\).
Intuitively, a pre-ideal collection of subcubes is closed under arbitrary unions and intersections, so long as those unions and intersections are actual subcubes. We note that property 4.5 above is equivalent to \(\mathcal{J} = \lambda( \mathcal{J} )\).
Lemma 4.6. A collection of subcubes is ideal if and only if it is pre-ideal. For all \(\mathcal{J} \in \mathrm{A} ^ \mathcal{T} (n)\) and all \(g \in { \mathrm{F} }^\mathrm{T} (n)\), we have \[\mathcal{T} ( F_ \mathcal{T} ( \mathcal{J} ) ) = \mathcal{J}, \qquad F_ \mathcal{T} ( \mathcal{T} (g) ) = g.\]
Proof. The proof uses a similar structure to that of Lemma 4.5.
Firstly, \(F_ \mathcal{T} ( \mathcal{J} )\) is trapping. (The proof is the same as its counterpart for \(F_ \mathcal{P} ( \mathcal{Q} )\).)
Secondly, we prove that \(\mathcal{T} ( g )\) is pre-ideal. First, \(\mathbb{B}^n\) is a trapspace of \(g\), hence \(\mathbb{B}^n \in \mathcal{J}\). Second, if \(A\) and \(B\) are trapspaces with non-empty intersection, let \(x \in A \cap B\), then \(g( x ) \in A \cap B\), hence \(A \cap B\) is also a trapspace. Third, if \(R = \bigcup \mathcal{R}\) for some \(\mathcal{R} \subseteq \mathcal{J}\), then for any \(x \in R\), there exists \(A \in \mathcal{J}\) such that \(x \in A\) and hence \(g( x ) \in A \subseteq R\), thus \(R\) is also a trapspace.
Since any ideal collection of subcubes is of the form \(\mathcal{T} (g)\) for some trapping network \(g\), we have just shown that any ideal collection of subcubes is pre-ideal.
Thirdly, we prove that \(\mathcal{T} ( F_ \mathcal{T} ( \mathcal{J} ) ) = \mathcal{J}\) for any pre-ideal collection \(\mathcal{J}\) of subcubes of \(\mathbb{B}^n\). Let \(g = F_ \mathcal{T} ( \mathcal{J} )\) so that \([ x, g(x) ] = \mathcal{J}(x) \in \mathcal{J}\) for all \(x \in \mathbb{B}^n\). Suppose \(A \in \mathcal{J}\), then for all \(x \in A\), \(g(x) \in \mathcal{J}(x) \subseteq A\), hence \(A \in \mathcal{T} ( g )\). Conversely, suppose \(B \in \mathcal{T} ( g )\), then \(B = \bigcup \{ \mathcal{J}(x) : x \in B \}\), whence \(B \in \mathcal{J}\) since \(\mathcal{J}\) is pre-ideal.
We have just shown that any pre-ideal collection of subcubes is ideal. Together with the previous item, we have proved that a collection of subcubes is ideal if and only if it is pre-ideal.
Fourthly, we prove that \(F_ \mathcal{T} ( \mathcal{T} ( g ) ) = g\) for all \(g \in { \mathrm{F} }^\mathrm{T} (n)\). Let \(\mathcal{Q} = \mathcal{T} ( g )\), so that \(\mathcal{Q}(x) = [ x, g(x) ]\) for all \(x \in \mathbb{B}^n\) since \(g\) is trapping. Thus \(g = F_ \mathcal{T} ( \mathcal{Q} )\) by definition of \(F\). \(\square\)
We now prove item 4.3.
Lemma 4.7. For all \(\mathcal{Q} \in \mathrm{A} ^ \mathcal{P} ( n )\) and all \(\mathcal{J} \in \mathrm{A} ^ \mathcal{T} ( n )\), we have \[\lambda_ \mathcal{P} ( \mathcal{Q} ) = \mathcal{T} ( F_ \mathcal{P} ( \mathcal{Q} ) ), \qquad \mu_ \mathcal{T} ( \mathcal{J} ) = \mathcal{P} ( F_ \mathcal{T} ( \mathcal{J} ) ).\]
Proof. We first prove that \(\lambda_ \mathcal{P} ( \mathcal{Q} ) = \mathcal{T} ( F_ \mathcal{P} ( \mathcal{Q} ) )\). Let \(g = F_ \mathcal{P} ( \mathcal{Q} )\). By Lemma 4.5, \(g\) is trapping with collection of principal trapspaces \(\mathcal{P} ( g ) = \mathcal{Q}\). Therefore its collection of trapspaces is given by any union of elements of \(\mathcal{Q}\) that form a subcube, i.e. \(\mathcal{T} ( g ) = \lambda_ \mathcal{P} ( \mathcal{Q})\).
We now prove that \(\mu_ \mathcal{T} ( \mathcal{J} ) = \mathcal{P} ( F_ \mathcal{T} ( \mathcal{J} ) )\). Again, let \(g = F_ \mathcal{T} ( \mathcal{J} )\); then \(g\) is trapping with collection of trapspaces \(\mathcal{T} ( g ) = \mathcal{J}\). Therefore, \(\mathcal{P} ( g ) = \{ \bigcap_{x \in A, A \in \mathcal{J}} A : x \in \mathbb{B}^n \} = \mu_ \mathcal{T} ( \mathcal{J} )\). \(\square\)
Item 4.3 immediately follows.
Corollary 4.8. For all \(\mathcal{Q} \in \mathrm{A} ^ \mathcal{P} ( n )\) and all \(\mathcal{J} \in \mathrm{A} ^ \mathcal{T} ( n )\), we have \[\mu_ \mathcal{T} ( \lambda_ \mathcal{P} ( \mathcal{Q} ) ) = \mathcal{Q}, \qquad \lambda_ \mathcal{P} ( \mu_ \mathcal{T} ( \mathcal{J} ) ) = \mathcal{J}.\]
Part of the theory built for principal trapspaces and trapping networks in the prequel of this section can be adapted to study minimal trapspaces instead.
We first note that the collection \(\mathcal{M} (f)\) of minimal trapspaces of \(f\) does not determine the collection \(\mathcal{P} (f)\) of principal trapspaces of \(f\). For instance, consider the following two networks, given by their respective asynchronous graphs below. They have the same collection of minimal trapspaces, namely the two fixed points, but the line \(\{ x_1 = 1 \}\) is a principal trapspace of the first network but not of the second.
Since the trapping closure of \(f\) satisfies \({f}^\mathrm{T} = F( \mathcal{P} (f) )\), we define the min-trapping extension of \(f\) by \[{f}^\mathrm{M} = F( \mathcal{M} (f) ).\]
More explicitly, say \(x\) is a min-trapspace configuration of \(f\) if it belongs to a minimal trapspace of \(f\) and denote the set of min-trapspace configurations of \(f\) by \(M(f)\). Then the min-trapping extension of \(f\) is given by \[{f}^\mathrm{M} ( x ) = \begin{cases} T_f( x ) – x & \text{if } x \in M(f) ,\\ \neg x & \text{otherwise}. \end{cases}\]
The min-trapping extension is not a closure operator, as below we display two networks \(f\) and \(g\) such that \(f \sqsubseteq g\) but \({f}^\mathrm{M} \not\sqsubseteq {g}^\mathrm{M}\).
The min-trapping extension does satisfy all the other properties that we expect. The proof of Lemma 4.9 is straightforward and hence omitted.
Lemma 4.9. For any \(f \in \mathrm{F} ( n )\), the following hold.
Say a network \(g\) is min-trapping if \(g = {g}^\mathrm{M}\) and denote the set of min-trapping networks in \(\mathrm{F} (n)\) by \({ \mathrm{F} }^\mathrm{M} ( n )\). The min-trapping extension of \(f\) is a trapping network that satisfies \({f}^\mathrm{T} \sqsubseteq {f}^\mathrm{M}\), as such we have \[{f}^\mathrm{M} = { ( {f}^\mathrm{M} ) }^\mathrm{T} = { ( {f}^\mathrm{T} ) }^\mathrm{M} = { ( {f}^\mathrm{M} ) }^\mathrm{M} .\]
We now give the analogue of Theorem 4.1 for min-trapping extensions.
Theorem 4.10. The following are equivalent for \(f, g \in \mathrm{F} (n)\):
(a) \(\mathcal{M} (f) = \mathcal{M} (g)\);
(b) \(M(f) = M(g)\) and \(T_f( x ) = T_g( x )\) for all \(x \in M(f)\);
(c) \(T_f( x ) = T_g( x )\) for all \(x \in M(f) \cup M(g)\);
(d) \({f}^\mathrm{M} = {g}^\mathrm{M}\).
Proof. (a)\(\implies\)(b). We have \(M(f) = \{ x \in A : A \in \mathcal{M} (f) \} = \{ x \in A : A \in \mathcal{M} (g) \} = M(g)\). Now, for any \(x \in M(f)\), \(x\) belongs to a unique minimal trapspace of \(f\), namely \(T_f(x)\); since \(M(f) = M(g)\), \(x\) belongs to a unique minimal trapspace of \(g\), namely \(T_g(x)\). Therefore, \(T_f(x) = T_g(x)\).
(b)\(\implies\)(c). Trivial.
(c)\(\implies\)(b). For the sake of contradiction, suppose that \(x \in M(f) \setminus M(g)\), so that \(T_f(x) = T_g(x)\). Let \(y \in T_g(x) \cap M(g)\), then \(T_f(y) = T_g(y) \subset T_g(x) = T_f(x)\), and hence \(x \notin M(f)\), which is the desired contradiction. Thus \(M(f) \subseteq M(g)\), and by symmetry we obtain \(M(f) = M(g)\).
(b)\(\implies\) (d). By definition of the min-trapping extension.
(d) \(\implies\)(a). We have \(\mathcal{M} ( f ) = \mathcal{M} ( {f}^\mathrm{M} ) = \mathcal{M} ( {g}^\mathrm{M} ) = \mathcal{M} ( g )\). \(\square\)
Say a collection of subcubes \(\mathcal{N} \in \mathrm{A} (n)\) is min-ideal if all its elements are disjoint: \(A \cap B = \emptyset\) for all \(A \ne B \in \mathcal{N}\). We denote the set of all min-ideal collections of subcubes of \(\mathbb{B}^n\) by \(\mathrm{A} ^ \mathcal{M} (n)\), and the restriction of the mapping \(F\) to \(\mathrm{A} ^ \mathcal{M} (n)\) as \(F_ \mathcal{M}\).
Theorem 4.11. The set of min-trapping networks is in bijection with the set of min-ideal collections of subcubes. More precisely, for all min-ideal collections of subcubes \(\mathcal{N} \in \mathrm{A} ^ \mathcal{M} (n)\) and all min-trapping networks \(g \in { \mathrm{F} }^\mathrm{M} ( n )\), we have \[\mathcal{M} ( F_ \mathcal{M} ( \mathcal{N} ) ) = \mathcal{N}, \qquad F_ \mathcal{M} ( \mathcal{M} ( g ) ) = g.\]
Proof. We first prove that \(\mathcal{M} ( F_ \mathcal{M} ( \mathcal{N} ) ) = \mathcal{N}\) for any min-ideal collection \(\mathcal{N}\). Let \(N = \bigcup_{A \in \mathcal{N}} A\) denote the content of \(\mathcal{N}\). For any \(x \in \mathbb{B}^n\), we have \[\mathcal{N}(x) = \begin{cases} A & \text{if } x \in A, A \in \mathcal{N} ,\\ \mathbb{B}^n & \text{if } x \notin N. \end{cases}\]
Therefore, \(g = F_ \mathcal{M} ( \mathcal{N} )\) is given by \[g( x ) = \begin{cases} A – x & \text{if } x \in A, A \in \mathcal{N} ,\\ \neg x & \text{if } x \notin N. \end{cases}\]
We obtain that \(\mathcal{M} ( g ) = \mathcal{N}\).
We now prove that \(F_ \mathcal{M} ( \mathcal{M} ( g ) ) = g\) for any min-trapping network \(g\). Let \(\mathcal{N} = \mathcal{M} ( g )\), so that \(\mathcal{N} = \{ T_g( x ) : x \in M(g) \}\) is min-ideal. Thus, \[\mathcal{N}(x) = \begin{cases} T_g(x) & \text{if } x \in M(g) ,\\ \mathbb{B}^n & \text{otherwise}, \end{cases}\] and \[F_ \mathcal{M} ( \mathcal{N} )(x) = \begin{cases} T_g(x) – x & \text{if } x \in M(g) ,\\ \neg x & \text{otherwise}, \end{cases} = {g}^\mathrm{M} ( x ) = g(x).\] \(\square\)
In [7], Bridoux et al. introduce commutative networks, where asynchronous updates can be performed in any order without altering the result. This subsection is devoted to a review of some of the results in [7]. Foremost, the authors of [7] are interested in possibly infinite networks, and hence distinguish between so-called locally and globally commutative networks. However, these two concepts coincide for the finite Boolean networks we study in this paper. As such, we say a network \(f \in \mathrm{F} (n)\) is commutative if it satisfies the following three equivalent properties:
(a) for all \(i, j \in [n]\), \(f^{ (i, j) } = f^{ (j, i) }\);
(b) for all \(S, T \subseteq [n]\), \(f^{ (S, T) } = f^{ (T, S)}\);
(c) for all \(S, T \subseteq [n]\) with \(S \cap T = \emptyset\), \(f^{ (S, T) } = f^{ (S \cup T) }\).
Commutative networks have some strong structural properties. Intuitively, they all stem from the key property that any update can be “serialised”, i.e. for any \(S = \{ s_1, \dots, s_k \} \subseteq [n]\), we have \[f^{(S)} = f^{(s_1, \dots, s_k)} = f^{(s_k)} \circ \dots \circ f^{(s_1)}.\]
For instance, for any property \(P\) of Boolean networks, we say \(f\) is locally \(P\) if \(f^{(i)}\) satisfies \(P\) for all \(i \in [n]\) and globally \(P\) if \(f^{(S)}\) satisfies \(P\) for all \(S \subseteq [n]\). As such, a network \(f \in \mathrm{F} ( n )\) is bijective if \(f\) is a bijection (i.e., a permutation of \(\mathbb{B}^n\)); \(f\) is locally bijective if \(f^{(i)}\) is bijective for all \(i \in [n]\); \(f\) is globally bijective if \(f^{ (S) }\) is a bijection for all \(S \subseteq [n]\). If \(f\) is a locally bijective commutative network, then for all \(S \subseteq [n]\), \(f^{(S)} = f^{(s_k)} \circ \dots \circ f^{(s_1)}\) is also bijective, i.e. \(f\) is globally bijective. Bridoux et al. go further, and show that the following are equivalent for a commutative network:
(a) \(f\) is bijective;
(b) \(f\) is locally bijective;
(c) \(f\) is globally bijective.
Moreover, recall that \(f\) is idempotent if \(f^2 = f\). The following are also equivalent for a commutative network:
(a) \(f\) is idempotent;
(b) \(f\) is locally idempotent;
(c) \(f\) is globally idempotent.
Commutative networks have heavily constrained dynamics. Any function \(\phi : \mathbb{B}\to \mathbb{B}\) has transient length at most \(1\) and period at most \(2\), and hence \(\phi^3 = \phi\). We then call a network \(f\) dynamically local if \(f^3 = f\). Clearly, for any \(f \in \mathrm{F} (n)\) and any \(i \in [n]\) the update \(f^{(i)}\) is dynamically local. In fact, commutative networks are also dynamically local, i.e. they have transient length at most \(1\) and period at most \(2\). Moreover, a network \(f \in \mathrm{F} ( n )\) is involutive if \(f\) is an involution, i.e. \(f^2 = \mathrm{id}\). Any involutive network is bijective, and as seen above any bijective commutative network is involutive.
The pinnacle of the study of commutative Boolean networks in [7] is a full classification of the asynchronous graphs of commutative networks. We give an overview of the classification below, and guide the reader to [7] for more detail. The classification takes three main steps: arrangement, arrangement network, and union of arrangement networks.
First, a family of subcubes \(\mathcal{X}\) is called an arrangement if \(Y := \bigcap_{X \in \mathcal{X}} X\) is a non-empty subcube. We denote the content of \(X\) by \(\hat{\mathcal{X}} := \bigcup_{X \in \mathcal{X}} X\). We say \(i \in [n]\) is a free dimension of \(\mathcal{X}\) if, for any \(x \in \hat{\mathcal{X}}\), \(y = (\neg x_i, x_{-i}) \in \hat{\mathcal{X}}\) as well. Six examples of arrangements are displayed below.
Second, an arrangement network intuitively only works on \(\hat{\mathcal{X}}\), converges towards \(Y\), and is uniform on any free dimension of \(\mathcal{X}\). More formally, an arrangement network satisfies: \(f(x) = x\) if \(x \notin \hat{\mathcal{X}}\), \(f(x) \in Y\) for all \(x \in \hat{\mathcal{X}}\), and \(f_i(x) = f_i(y)\) for all \(x,y \in \hat{\mathcal{X}}\) with \(x_i = y_i\). Arrangement networks are clearly commutative. There are three possible arrangement networks for the arrangement in the bottom row, centre column above. They are displayed below.
Third, one can take the union of arrangement networks, provided their respective arrangement contents are disjoint, by taking the union of their asynchronous graphs. Three examples are displayed below.
We can now give the classification theorem.
Theorem 5.1 (Classification of asynchronous graphs of commutative networks [7]). A Boolean network is commutative if and only if it is a union of arrangement networks.
We shall focus on two special cases of commutative networks. On the one hand, a negation on subcubes is a union of arrangement networks, where each arrangement \(X\) is a single subcube, and \(f_i(x) = \neg x_i\) for each \(x \in X\). Two examples are displayed below.
On the other hand, a constant on arrangements is a union of arrangements, where for each arrangement \(X\), \(f(x) = f(y)\) for all \(x,y \in X\). Two examples are displayed below.
We immediately see that negations on subcube are exactly the commutative networks with symmetric asynchronous graphs, and similarly the constants on arrangements are exactly the commutative networks with oriented asynchronous graphs.
This subsection is devoted to comparing commutative networks to trapping networks. Recall (Theorem 3.4) that a network is trapping if and only if for any \(x \in \mathbb{B}^n\) and any \(y \in [x, f(x)]\), \[[y, f(y)] \subseteq [x, f(x)].\]
Theorem 5.2 (Alternate definitions of commutative networks). Any commutative network is trapping. More precisely, the following are equivalent for \(f \in \mathrm{F} ( n )\):
(a) \(f\) is commutative, i.e. \(f^{ (i,j) } = f^{ (j,i) }\) for all \(i,j \in [n]\).
(b) \([y, f(x)] \subseteq [y, f(y)] \subseteq [x, f(x)]\) for all \(x \in \mathbb{B}^n\) and any \(y \in [x, f(x)]\).
(c) \(f^{ (S \Delta T) } \sqsubseteq f^{( S,T )} \sqsubseteq f^{( S \cup T )}\) for all \(S, T \subseteq [n]\).
Proof. (a) \(\implies\) (b). Let \(f\) be a commutative network, \(x \in \mathbb{B}^n\) and \(y \in [x, f(x)]\). Denote \(y = f^{(S)}(x)\) for some \(S = \Delta( x, y ) \subseteq \Delta( x, f(x) )\). We first prove \([y, f(y)] \subseteq [x, f(x)]\). For all \(i \notin \Delta( x, f(x) )\), we have \[f_i( y ) = f_i( f^{(S)}( x ) ) = f_i( x ) = x_i = y_i,\] hence \(i \notin \Delta( y, f(y) )\). We now prove that \([y, f(x)] \subseteq [y, f(y)]\). For all \(j \in \Delta( y, f(x) ) = \Delta( x, f(x) ) \setminus S\), we have \[f_j( y ) = f_j( f^{(S)}( x ) ) = f_j( x ) \ne x_j = y_j,\] hence \(j \in \Delta( y, f(y) )\).
(b) \(\implies\) (a). Suppose, for the sake of contradiction, that \(f\) is not commutative, i.e. there exist \(i, j \in [n]\) and \(x \in \mathbb{B}^n\) such that \(f_i( f^{(j)}( x ) ) \ne f_i( x )\). Denoting \(y = f^{(j)}( x )\), we have \(y \in [x, f(x)]\). If \(i \in \Delta( x, f(x) )\), then \(\Delta( y, f(x) ) \not\subseteq \Delta( y, f(y) )\); if \(i \notin \Delta( x, f(x) )\), then \(\Delta( y, f(y) ) \not\subseteq \Delta( x, f(x) )\). In either case, we obtain a contradiction.
(a) \(\implies\) (c). Since \(f\) is trapping, we have \(f^{( S,T )} \sqsubseteq f^{(S \cup T)}\). Moreover, by commutativity, \[f^{(S,T)} = f^{( S \Delta T, S \cap T, S \cap T )},\] and hence \(f^{(S,T)}_{S \Delta T} = f_{S \Delta T}\), which implies \(f^{ (S \Delta T) } \sqsubseteq f^{( S,T )}\).
(c) \(\implies\) (a). If \(S \cap T = \emptyset\), we have \(S \Delta T = S \cup T\) and hence \(f^{( S,T )} = f^{ (S \cup T) }\). Therefore, \(f\) is commutative. \(\square\)
We now classify the collections of principal trapspaces of commutative networks. Say a collection of subcubes \(\mathcal{A} \in \mathrm{A} ( n )\) is convex if the following holds: for all \(Q, R \in \mathcal{A}\) and any \(S\) with \(Q \subseteq S \subseteq R\), \(S \in \mathcal{A}\).
Theorem 5.3 (Commutative networks and convex collections of principal trapspaces). A pre-principal collection of subcubes is the collection of principal trapspaces of a commutative network if and only if it is convex.
We begin the proof with a technical lemma. For any \(f \in \mathrm{F} (n)\) and any \(x \in \mathbb{B}^n\), denote the dimension of \(T_f(x)\) as \(\delta_x = d_\mathrm{H}( x, f(x) )\).
Lemma 5.4. Let \(f\) be a commutative network. For any \(y \in [x, f(x)]\), we have \[d_\mathrm{H}(x, y) \ge \delta_x – \delta_y \ge 0,\] and \(d_\mathrm{H}(x, y) = \delta_x – \delta_y\) if and only if \(f(y) = f(x)\).
Proof. Let \(x \in \mathbb{B}^n\) and \(y \in [x, f(x)]\). Firstly, since \(f(y) \in [x, f(x)]\), we immediately obtain \(\delta_x \ge \delta_y\). Secondly, we have \[\delta_y + d_\mathrm{H}( x, y ) = d_\mathrm{H}( y, f(y) ) + d_\mathrm{H}( x, y ) \ge d_\mathrm{H}( y, f(x) ) + d_\mathrm{H}( x, y ) \ge d_\mathrm{H}( x, f(x) ) = \delta_x,\] where we used Theorem 5.2 to show \(d_\mathrm{H}( y, f(y) ) \ge d_\mathrm{H}( y, f(x) )\). Thirdly, by the above, we have \(d_\mathrm{H}(x, y) = \delta_x – \delta_y\) only if \(d_\mathrm{H}( y, f(y) ) = d_\mathrm{H}( y, f(x) )\). Since \(f(x) \in [y, f(y)]\), this is equivalent to \(f(x) = f(y)\). Finally, if \(f(x) = f(y)\), then \[\delta_x = d_\mathrm{H}( x, f(x) ) = d_\mathrm{H}( x, y ) + d_\mathrm{H}( y, f(x) ) = d_\mathrm{H}( x, y ) + d_\mathrm{H}( y, f(y) ) = d_\mathrm{H}( x, y ) + \delta_y.\] \(\square\)
Proof of Theorem 5.3. Let \(f\) be a commutative network. Now, suppose that \(T_f( y ) \subseteq T_f( x )\) and that \(x\) and \(y\) are nearest possible, i.e. if \(T_f( x’ ) = T_f( x )\) and \(T_f( y’ ) \subseteq T_f( y )\), then \(d_\mathrm{H}( x, y ) \le d_\mathrm{H}( x’, y’ )\).
Claim 1. With the conditions above, \(f(x) = f(y)\).
Proof. We first prove that \(y \in [x, f(y)]\). If there exists \(i \in \Delta( y, f(y) ) \cap \Delta( x, y )\), then \(y’ = y + e_i\) satisfies \(T_f( y’ ) \subseteq T_f( y )\) and \(d_\mathrm{H}( x, y’ ) = d_\mathrm{H}( x, y ) – 1\), which contradicts our assumptions. Therefore, \(\Delta( y, f(y) ) \cap \Delta( x, y ) = \emptyset\). We obtain that for all \(j \in [n]\), \[y_j \ne x_j \implies y_j = f( y )_j \ne x_j,\] which is equivalent to \(\Delta( y, x ) \subseteq \Delta( x, f(y) )\). Similarly, we obtain \(\Delta( y, f(y) ) \subseteq \Delta( x, f(y) )\). Thus, \(y \in [x, f(y)]\).
Now, \(f(x) \in [y, f(y)]\) because \(f\) is commutative, hence \[[ x, f(y) ] = [ x, y, f(y) ] = [ x, y, f(y), f(x) ] = [x, f(x)],\] thus \(f(y) = f(x)\). \(\square\)
Any subcube \(S\) satisfying \(T_f(y) = [y, f(x)] \subseteq S \subseteq [x, f(x)] = T_f(x)\) can be expressed as \(S = [z, f(x)]\) for some \(z \in [x, y]\). Therefore, we only need to prove that \(f(z) = f(x)\) for all \(z \in [x, y]\). Since \(z = f^{(\Delta(x, z))}( x )\), we obtain \[f^{( \Delta(z,y) )}( z ) = f^{( \Delta(z,y) )}( f^{( \Delta(x, z) )} ( x ) ) = f^{(\Delta(x,y))}( x ) = y.\]
Therefore, \(y \in [z, f(z)]\). We now repeatedly use Lemma 5.4. Since \(f(y) = f(x)\), we have \(d_\mathrm{H}( x, y ) = \delta_x – \delta_y\). We obtain \[d_\mathrm{H}( x, y ) = \delta_x – \delta_y = ( \delta_x – \delta_z ) + ( \delta_z – \delta_y ) \le d_\mathrm{H}( x, z ) + d_\mathrm{H}( z,y ) = d_\mathrm{H}( x, y ),\] thus \(d_\mathrm{H}( x, z ) = \delta_x – \delta_z\), and hence \(f(z) = f(x)\), and we are done.
Conversely, suppose \(\mathcal{A}\) is a convex pre-principal collection of subcubes and let \(f = F_ \mathcal{P} ( \mathcal{A} )\); recall that \(f\) is trapping. We only need to prove that \(f(x) \in [y, f(y)]\) for all \(x \in \mathbb{B}^n\), \(y \in [x, f(x)]\). Suppose, for the sake of contradiction, that \(f(x) \notin [y, f(y)]\), say \(f_j(x) \ne y_j = f_j(y)\) for some \(j \in \Delta( x, f(x) )\). Then \[[y, f(y)] \subseteq [x, y, f(y)] \subseteq [x, f(x)],\] and by convexity, \([x, y, f(y)]\) is a principal trapspace of \(f\), that must contain \(f(x)\). But \(f_j(x) \notin \{ x_j, y_j, f_j(y) \}\), hence \(f(x) \notin [x, y, f(y)]\), which is the desired contradiction. \(\square\)
A network is Marseille if it is commutative and bijective. As seen above, this is equivalent to commutative and locally bijective, and equivalent to commutative and globally bijective.
As expected, Marseille networks are exactly the negations on subcubes.
Theorem 6.1 (Alternate definitions of Marseille networks). The following are equivalent for \(f \in \mathrm{F} ( n )\):
(a) \(f\) is Marseille, i.e. \(f\) is commutative and bijective.
(b) \(f\) is a negation on subcubes.
(c) for all \(x \in \mathbb{B}^n\) and \(y \in [x, f(x)]\), \([y, f(y)] = [x, f(x)]\).
(d) for all \(S, T \subseteq [n]\), \(f^{ (S \Delta T) } = f^{( S,T )}\).
Proof. (a) \(\implies\) (c). Since \(f\) is commutative, we have \([ y, f(y) ] \subseteq [ x, f(x) ]\). Suppose \([ y, f(y) ] \subset [ x, f(x) ]\) for some \(y \in [x, f(x)]\); then \(x \notin [y, f(y)]\). We have \(y = f^{(S)}( x )\) for some \(S \subseteq [n]\); therefore \(f^{(S)}( T_f(y) \cup \{ x \} ) \subseteq T_f(y)\), which contradicts the fact that \(f^{(S)}\) is bijective.
(a) \(\iff\) (b). This easily follows from Theorem 5.1.
(c) \(\implies\) (a). By Theorem 5.2, \(f\) is commutative.
For the sake of contradiction, suppose that \(f\) is not bijective, i.e. there exist distinct \(x, y \in \mathbb{B}^n\) such that \(f( x ) = f( y )\). If \(y \in [x, f(x)]\), we have \([y, f(x)] = [y, f(y)] = [x, f(x)]\) and hence \(x = y\). Therefore, \(y \notin T_f(x)\) and \(x \notin T_f(y)\). But then, \(z = f(x)\) satisfies \(z \in [x, f(x)]\) and \(f(z) \in T_f(z) \subseteq T_f( x ) \cap T_f( y ) \subset T_f(x)\), hence \([z, f(z)] \ne [x, f(x)]\), which is the desired contradiction.
(a) \(\implies\) (d). We have \[f^{(S, T)} = f^{( S \Delta T, S \cap T, S \cap T )} = f^{(S \Delta T)}.\]
(d) \(\implies\)(a). \(f\) is clearly commutative, and \(f^{(S, S)} = \mathrm{id}\) for all \(S \subseteq [n]\), i.e. \(f\) is globally bijective. \(\square\)
Recall that a graph \(\Gamma\) is symmetric if \((u,v) \in E\) implies \((v,u) \in E\). We now investigate networks with symmetric (asynchronous, general asynchronous, trapping) graphs.
We shall represent the implications amongst different properties related to symmetric graphs in the diagram in Figure 2. We shall make use of such diagrams in Figures 3, 4 and 5 as well. In such diagrams, black arrows represent implications that hold for all Boolean networks, magenta arrows represent implications that hold for all trapping networks, and blue arrows represent implications that hold for all commutative networks.
We say that such a diagram is correct if all the implications depicted indeed hold; we say that it is complete if any other implication (that might hold for all networks, or all trapping networks, or all commutative networks) between the different properties of the diagram can be inferred from the diagram. For instance, in Figure 3, the implication “Commutative and Bijective \(\implies\) Marseille” can be inferred from the graph by following two arrows; on the other hand, there exists a counterexample to the implication “Trapping and Bijective \(\implies\) Locally Bijective.”
When proving the correctness of a diagram, we prove a sufficient subset of implications, such that any other implication follows from one in that subset. Similarly, when proving the completeness of a diagram, we exhibit a counterexample for each implication in a sufficient subset of incorrect implications.
The diagram in Figure 2 not only gives relations amongst symmetric asynchronous, general asynchronous, and trapping graphs. It also provides several alternate definitions of Marseille networks.
Theorem 6.2 (Graphs defined from networks: Symmetric graphs). The diagram in Figure 2 is correct and complete.
Proof. Firstly, we prove the triple equivalence Marseille \(\iff\) Globally Involutive \(\iff\) Symmetric \(\mathtt{GA}\).
(a) Marseille \(\implies\) Globally Involutive. Follows from the results on commutative networks reviewed in Section 5.1.
(b) Globally Involutive \(\implies\) Symmetric \(\mathtt{GA}\). If \(x \to_{ \mathtt{GA} (f)} x\) but \(y \not\to_{ \mathtt{GA} (f)} x\), we have \(y = f^{(S)}( x )\) for \(S = \Delta( x, y )\) but \(f^{(S)}( y ) \ne x\), hence \(f^{(S)}\) is not involutive.
(c) Symmetric \(\mathtt{GA}\) \(\implies\) Marseille. Let \(y \in [x, f(x)]\) and \(\Gamma = \mathtt{GA} ( f )\). Let us prove that \([x, f(x)] \subseteq [y, f(y)]\). We have \(x \to_\Gamma y\), hence by symmetry \(y \to_\Gamma x\) (or in other words, \(x \in [y, f(y)]\)). Moreover, we have \(x \to_\Gamma f(x)\), hence \(f(x) \to_\Gamma x\) and \(f(x) \to_\Gamma y\); and by symmetry \(y \to_\Gamma f(x)\) (or in other words, \(f(x) \in [y, f(y)]\)). We obtain \([x, f(x)] \subseteq [y, f(y)]\), as desired. Now, since \(x \in [y, f(y)]\), we obtain \([y, f(y)] \subseteq [x, f(x)]\); therefore \([x, f(x)] = [y, f(y)]\) and \(f\) is Marseille.
Secondly, we prove the other black implications and equivalences in Figure 2.
(d) Symmetric \(\mathtt{GA}\) \(\implies\) Symmetric \(\mathtt{T}\). \(f\) is Marseille, hence it is trapping and \(\mathtt{T} (f) = \mathtt{GA} (f)\).
(e) Symmetric \(\mathtt{GA}\) \(\implies\) Symmetric \(\mathtt{A}\). For any distinct \(x, y \in \mathbb{B}^n\), we have \[\begin{aligned} x \to_{ \mathtt{A} (f)} y &\implies x \to_{ \mathtt{GA} (f)} y \text{ and } d_\mathrm{H}(x,y) = 1\\ &\implies y \to_{ \mathtt{GA} (f)} x \text{ and } d_\mathrm{H}(x,y) = 1\\& \implies y \to_{ \mathtt{A} (f)} x. \end{aligned}\]
(f) Locally Bijective \(\iff\) Locally Involutive. \(f^{(i)}\) is dynamically local, hence it is bijective if and only if it is involutive.
(g) Locally Bijective \(\iff\) Symmetric \(\mathtt{A}\). Let \(f \in \mathrm{F} (n)\) and \(i \in [n]\). The function \(f^{ (i) }\) can be decomposed into \(2^{n-1}\) functions, one for each value of \(x_{-i}\). More formally, for any \(z \in \mathbb{B}^{n-1}\), let \(g^z : \mathbb{B}\to \mathbb{B}\) be defined by \(g^z( a ) = f_i(a, z)\) for all \(a \in \mathbb{B}\). For all \(z \in \mathbb{B}^{n-1}\), let \(\Gamma^z\) be the subgraph of \(\mathtt{A} (f)\) induced by \(\{ x = (x_i = 0, x_{-i} = z), y = (y_i = 1, y_{-i} = z) \}\). We note that \(g^z\) is bijective if and only if \(\Gamma^z\) is symmetric (either \(g^z\) is the identity, in which case \(\Gamma^z\) has two loops, or \(g^z\) is the transposition \((0, 1)\), in which case \(\Gamma^z\) is complete). We then have \(f^{ (i) }(x) = ( g^{ x_{-i} }( x_i ), x_{-i} )\), so that \(f^{ (i) }\) is bijective if and only if all \(g^z\) functions are bijective. Thus, \(f\) is locally bijective if and only if \(\mathtt{A} (f)\) is symmetric.
Thirdly, we prove the magenta implications in Figure 2, that only hold for trapping networks.
(h) Trapping and Symmetric \(\mathtt{T}\) \(\implies\) Symmetric \(\mathtt{GA}\). We have \(\mathtt{T} (f) = \mathtt{GA} (f)\).
(i) Trapping and Symmetric \(\mathtt{A}\) \(\implies\) Marseille. We prove that for all \(y \in [x, f(x)]\), \([y, f(y)] = [x, f(x)]\). The proof is by induction on the distance \(d_\mathrm{H}( x, y )\), and is clear for distance \(0\). Suppose it holds for distance \(d\), and suppose \(d_\mathrm{H}( x, y ) = d + 1\). Let \(z \in [x, y] \subseteq [x, f(x)]\) such that \(d_\mathrm{H}( x, z ) = d\) and \(d_\mathrm{H}( z, y ) = 1\). By induction hypothesis, \([z, f(z)] = [x, f(x)]\) and hence \(z \to_{ \mathtt{A} (f)} y\); by symmetry, \(y \to_{ \mathtt{A} (f)} z\), hence \([x, f(x)] = [z, f(z)] = T_f(z) \subseteq T_f(y) = [y, f(y)]\).
Finally, we exhibit counterexamples to implications that are not displayed in Figure 2.
(a) Symmetric \(\mathtt{T}\) \(\nRightarrow\) Symmetric \(\mathtt{A}\).
(b) Symmetric \(\mathtt{A}\) \(\nRightarrow\) Symmetric \(\mathtt{T}\).
\(\square\)
The forthcoming classification of Marseille networks as trapping networks will involve proving that bijective trapping networks are involutive. For the sake of completeness, we prove that all trapping networks have a period of at most \(2\), but their transient length can be up to \(n\).
Proposition 6.3. Let \(f \in { \mathrm{F} }^\mathrm{T} (n)\), then \(f^{n+2} = f^n\). Moreover, for all \(n \ge 3\), there exists a trapping network with period \(2\) and transient length \(n\).
Proof. For any \(x\), let \(O(x) = \{ f^i(x) : i \in \mathbb{N} \}\) be the orbit of \(x\). The sequence \(T_i := T_f( f^i(x) )\) for \(i \in \mathbb{N}\) is a descending chain of subcubes. If \(T_i = T_{i+1}\), then we have \([f^i(x), f^{i+1}(x)] = [f^{i+1}(x), f^{i+2}(x)]\), hence \(f^i(x) = f^{i+2}(x)\) and \(T_i = T_{i+1} = \dots = T_n\), and \(|O(x)| \le i+1\). Since \(T_0\) has dimension \(n\), we obtain \(T_n = T_{n+1}\) and hence \(|O(x)| \le n+1\). Therefore, \(f\) has transient length at most \(n\). Moreover, if \(x\) is a periodic point, say \(f^k(x) = x\) we have \(T_0 = T_{k+1}\), hence \(T_0 = T_1\) and \(x = f^2(x)\).
Conversely, the trapping network \(f\) with period \(2\) and transient length \(n \ge 3\) is constructed as follows. First, let \(t^1, \dots, t^{n+1} \in \mathbb{B}^n\) be defined as \[t^i_j = \begin{cases} 1 & \text{if } j < i, \\ i + j \mod 2 & \text{otherwise}. \end{cases}\]
For instance, for \(n = 4\) we obtain \[t^1 = 0101, \; t^2 = 1010, \; t^3 = 1101, \; t^4 = 1110, \; t^5 = 1111.\]
Second, let \(c^1 = 0 \dots 00\) and \(c^2 = 0 \dots 01\); note that \(c^i \ne t^j\) for all \(i \in \{1,2\}\) and \(j \in \{1, \dots, n+1\}\). Third, let \[f(x) = \begin{cases} t^{i+1} &\text{if } x = t^i, i \le n, \\ c^2 &\text{if } x = c^1, \\ c^1 &\text{if } x = c^2, \\ x &\text{otherwise}. \end{cases}\]
Then clearly, \(f\) has period \(2\) and transient length \(n\). It is easily shown that \(f\) is also trapping. \(\square\)
We now classify Marseille networks as specific trapping networks.
Theorem 6.4 (Classification of Marseille networks). The diagram in Figure 3 is correct and complete.
Proof. The implications in the top row of Figure 3 all follow from previous results. We now prove the remaining implications.
(a) Marseille \(\implies\) Involutive. Marseille is equivalent to Globally Involutive.
(b) Commutative and Involutive \(\implies\) Marseille. Trivial.
(c) Involutive \(\implies\) Bijective. Trivial.
(d) Trapping and Bijective \(\implies\) Involutive. Follows from Proposition 6.3.
We now exhibit counterexamples to implications that are not displayed in Figure 3.
(a) Trapping and Involutive \(\nRightarrow\) Locally Bijective.
(b) Bijective \(\nRightarrow\) Involutive.
\(\square\)
A network is Lille if it is commutative and idempotent. We begin this section with four alternative definitions of Lille networks.
Theorem 7.1 (Alternative definitions of Lille networks). The following are equivalent for \(f \in \mathrm{F} ( n )\).
(a) \(f\) is Lille, i.e. it is commutative and idempotent.
(b) \(f\) is a constant on arrangements.
(c) for all \(x \in \mathbb{B}^n\) and \(y \in [x, f(x)]\), \([y, f(y)] = [y, f(x)]\).
(d) for all \(S, T \subseteq [n]\), \(f^{( S,T )} = f^{ (S \cup T) }\).
Proof. (a) \(\iff\) (b). Follows from Theorem 5.1.
(a) \(\implies\) (c). If \(y \in [x, f(x)]\), we have \(y = f^{(S)}( x )\) for some \(S \subseteq [n]\). By idempotence of \(f^{(S)}\), we have \[f( y ) = f^{(S, [n] \setminus S)}( y ) = f^{(S, S, [n] \setminus S)}( x ) = f^{(S, [n] \setminus S)}( x ) = f( x ).\]
(c) \(\implies\) (a). \(f\) is commutative from Theorem 5.2. Suppose, for the sake of contradiction, that \(f^{(S)}\) is not idempotent for some \(S \subseteq [n]\), i.e. \(f^{(S)}(x) = y \ne f^{(S)}(y)\). Then \(y \in [x, f(x)]\) and yet \(f_S( y ) \ne f_S( x )\), and hence \(f(y) \ne f(x)\), which is the desired contradiction.
(a) \(\implies\) (d). We have \[f^{(S, T)} = f^{( S \Delta T, S \cap T, S \cap T )} = f^{(S \cup T)}.\]
(d) \(\implies\) (a). Clearly \(f\) is commutative, and \(f^{(S, S)} = f^{(S)}\) for all \(S \subseteq [n]\), i.e. \(f\) is globally idempotent. Thus, \(f\) is Lille. \(\square\)
A graph is oriented if \((u,v) \in E \implies (v,u) \notin E\) for all \(u \ne v\). Let us say that a graph is triangular if the only cycles in the graph are its loops; in other words, the vertices can be sorted such that the adjacency matrix is triangular. Say a graph is sink-terminal if all its terminal components have cardinality one.
Let us say a network is Distinct Principal Trapspaces (DPT) if \(T_f( x ) \ne T_f( y )\) for all \(x \ne y\); in other words, \(f\) is DPT if and only if \(\mathtt{T} ( f )\) triangular. A fixed point of \(f\) is a configuration \(x\) such that \(f(x) = x\); we denote the set of fixed points of \(f\) by \(\mathrm{Fix}( f )\). We say a network is Trapspace-FP if every trapspace of \(f\) contains a fixed point. The equivalence between Trapspace-FP and Sink-terminal \(\mathtt{T}\) is given in Lemma 7.2 below; its proof is straightforward and hence omitted. We strengthen this notion in two ways: a network is Interval-FP if every interval contains a fixed point; it is Interval-UFP if every interval contains a unique fixed point.
Recall that a Boolean network is fixable if and only if there is a word \(w\) over the alphabet \([n]\) such that \(f^w(x)\) is a fixed point for all \(x\) [2]. Equivalently, \(f\) is fixable if and only if all its asynchronous attractors are fixed points, i.e. \(\mathtt{A} ( f )\) is sink-terminal.
Lemma 7.2. Let \(f \in \mathrm{F} ( n )\). The following are equivalent:
(a) \(\mathtt{T} ( f )\) is sink-terminal;
(b) for any \(x \in \mathbb{B}^n \setminus \mathrm{Fix}( f )\), there exists \(y \in T_f(x)\) with \(T_f( y ) \subset T_f( x )\);
(c) the fixed points of \(f\) are the only minimal trapspaces of \(f\), i.e. \(M(f) = \mathrm{Fix}(f)\);
(d) any principal trapspace of \(f\) contains a fixed point;
(e) \(f\) is trapspace-FP, i.e. any trapspace of \(f\) contains a fixed point.
Theorem 7.3 (Graphs defined from networks: Triangular graphs). The diagram in Figure 4 is correct and complete.
Proof. All the one-way black implications in Figure 4, such as “Triangular \(\mathtt{T}\) \(\implies\) Triangular \(\mathtt{GA}\)” all follow from some basic facts about the graphs; as such, we omit their proofs.
We begin by proving all the equivalences in Figure 4.
(a) Locally Idempotent \(\iff\) Oriented \(\mathtt{A}\). For all \(i \in [n]\) one can decompose \(f_i\) as \(2^{n-1}\) functions \(f_{i,a} : \mathbb{B}\to \mathbb{B}\) for all \(a \in \mathbb{B}^{n-1}\) as follows. For any \(\alpha \in \mathbb{B}\), let \(y \in \mathbb{B}^n\) such that \(y_i = \alpha\) and \(y_{-i} = a\), then \(f_{i,a}( \alpha ) = f_i( y )\). Then \(f^{(i)}\) is idempotent if and only if \(f_{i,a}\) is idempotent for all \(a \in \mathbb{B}^{n-1}\), which in turn is equivalent to all arcs \(( x, f^{(i)}(x) )\) in \(\mathtt{A} (f)\) being oriented.
(b) Trapspace-FP \(\iff\) Sink-terminal \(\mathtt{T}\). From Lemma 7.2.
(c) Fixable \(\iff\) Sink-terminal \(\mathtt{A}\). Trivial.
(d) DPT \(\iff\) Triangular \(\mathtt{T}\). By definition.
(e) Triangular \(\mathtt{T}\) \(\iff\) Oriented \(\mathtt{T}\). A transitive graph is oriented if and only if it is triangular.
We now prove all the magenta implications in Figure 4, which hold for all trapping networks.
(f) Trapping and Oriented \(\mathtt{GA}\) \(\implies\) Triangular \(\mathtt{T}\). In this case, \(\mathtt{GA} = \mathtt{T}\) is transitive and oriented, and hence triangular.
(g) Trapping and Oriented \(\mathtt{A}\) \(\implies\) Triangular \(\mathtt{A}\). For the sake of contradiction, suppose there is a cycle in \(\mathtt{A} ( f )\), say \(x \to \dots \to y \to x\). Then \(y \in T_f( x )\) and \(d_\mathrm{H}( x, y ) = 1\), hence \(x \to y\) in \(\mathtt{A} ( f )\). Thus, the asynchronous graph is not oriented, which is the desired contradiction.
(h) Trapping and Trapspace-FP \(\implies\) Fixable. By Lemma 7.2, wWe only need to prove that if for any \(x \in \mathbb{B}^n \setminus \mathrm{Fix}( f )\), there exists \(y \in T_f(x)\) with \(T_f( y ) \subset T_f( x )\), then \(f\) is fixable. Suppose that, for the sake of contradiction, \(x\) does not reach a configuration with a smaller principal trapspace. Let \(A(x) \subseteq T_f(x)\) be the set of configurations reachable from \(x\) in \(\mathtt{A} ( f )\); by our hypothesis, \(T_f(a) = T_f( x )\) for all \(a \in A(x)\). We prove by induction on \(d\) that \(A( x )\) contains all the configurations \(y \in T_f( x )\) at Hamming distance at most \(d\) from \(x\). The claim is clear for \(d = 0\), hence suppose it holds for \(d\). If \(d \ge d_\mathrm{H}( x, f(x) )\), there is nothing to prove, hence suppose \(d \le d_\mathrm{H}( x, f(x) ) – 1\) and let \(y \in T_f( x )\) such that \(d_\mathrm{H}( x, y ) = d + 1\). Let \(i \in \Delta(x, y)\), so that the configuration \(a = (\neg y_i, y_{-i})\) satisfies \(a \in T_f( x )\) and \(d_\mathrm{H}( a,x ) = d\), and by induction hypothesis, \(a \in A(x)\). Since \(N^{out}( \mathtt{GA} (f); a ) = T_f( x )\), we have \(i \in \Delta( a, f(a) )\) and hence \(a \to y\) in \(\mathtt{A} ( f )\); thus, \(y \in A(x)\) and the claim is proved. Thus, for any \(y \in T_f(x)\), we have \(T_f(y) = T_f(x)\), which is the desired contradiction.
We now prove all the blue implications in Figure 4, that hold for all commutative networks.
(i) Commutative and Locally Idempotent \(\implies\) DPT. Anticipating a result below, let us prove that \(f(y) = f(x)\) for all \(y \in [x, f(x)]\) (and hence they have distinct principal trapspaces). We have \(y = f^{(S)}( x )\) for some \(S \subseteq [n]\), and hence \[f(y) = f^{(S, S, [n] \setminus S)}( x ) = f(x).\]
(j) Commutative and Fixable \(\implies\) Oriented \(\mathtt{A}\). Thanks to Theorem 5.1, if \(f\) is commutative and \(\mathtt{A} ( f )\) is not oriented, then there is a connected component of \(\mathtt{A} ( f )\) that does not contain a fixed point, and hence \(f\) is not fixable.
We finally exhibit counterexamples to implications that are not displayed in Figure 4.
(a) Triangular \(\mathtt{GA}\) \(\nRightarrow\) Triangular \(\mathtt{T}\).
(b) Trapping and Triangular \(\mathtt{A}\) \(\nRightarrow\) Oriented \(\mathtt{GA}\).
(c) Oriented \(\mathtt{GA}\) \(\nRightarrow\) Sink-terminal \(\mathtt{T}\).
(d) Sink-terminal \(\mathtt{T}\) \(\nRightarrow\) Sink-terminal \(\mathtt{GA}\).
(e) Sink-terminal \(\mathtt{GA}\) \(\nRightarrow\) Sink-terminal \(\mathtt{A}\).
(f) Trapping and Sink-terminal \(\mathtt{A}\) \(\nRightarrow\) Oriented \(\mathtt{A}\).
\(\square\)
In this subsection, we give alternate definitions for globally idempotent networks.
Theorem 7.4 (Alternate definitions of globally idempotent networks). Globally idempotent networks are trapping. More precisely, the following are equivalent for \(f \in \mathrm{F} (n)\):
(a) \(f\) is globally idempotent, i.e. \(f^{(S,S)} = f^{(S)}\) for all \(S \subseteq [n]\).
(b) \([y, f(y)] \subseteq [y, f(x)]\) for all \(x \in \mathbb{B}^n\) and any \(y \in [x, f(x)]\).
(c) \(f^{(S, T)} \sqsupseteq f^{(S \cap T)}\) for all \(S, T \subseteq [n]\).
Proof. (a) \(\implies\) (b). Let \(x \in \mathbb{B}^n\) and \(y \in [x, f(x)]\). For any \(i \in \Delta( y, f(y) )\), we have \(y_i \ne f_i(y) = f_i(x)\), hence \(i \in \Delta( y, f(x) )\).
(b) \(\implies\) (a). Suppose, for the sake of contradiction, that there exist \(S \subseteq [n]\), \(i \in S\), and \(x \in \mathbb{B}^n\) such that \(f_i( f^{(S)}(x) ) \ne f_i( x )\). Since \(f^{(S)}( x ) = f^{(S \cap \Delta(x, f(x)))}( x )\), we can assume \(S \subseteq \Delta( x, f(x) )\). Denoting \(y = f^{(S)}( x )\), we have \(y \in [x, f(x)]\), \(y_i = f_i( x ) = \neg f_i( y )\). Thus, \(i \in \Delta( y, f(y) ) \subseteq \Delta( y, f(x) )\), which is the desired contradiction.
(a) \(\implies\) (c). \(f\) is trapping, hence \(f^{( S,T )} \sqsubseteq f^{( S \cup T )}\). Moreover, \[f^{(S, T)} = f^{( S, T \setminus S)},\] and hence \(f^{(S, T)}_{ S \cap T } = f_{S \cap T}\), which implies \(f^{ (S \cap T) } \sqsubseteq f^{( S,T )}\).
(c) \(\implies\) (a). We have \(f^{(S)} = f^{(S, S)}\) for all \(S \subseteq [n]\), i.e. \(f\) is globally idempotent. \(\square\)
Theorem 7.5 (Classification of Lille networks). The diagram in Figure 5 is correct and complete.
Proof. Once again, all the unidirectional black implications are either trivial or follow previous results; as such, their proofs are omitted.
We now prove the magenta implications, that only hold for trapping networks (and that are not direct consequences of their counterparts in Figure 4).
(a) Trapping and Trapspace-FP \(\implies\) Interval-FP. Every interval is a principal trapspace, and hence it contains a fixed point.
(b) Trapping and Interval-UFP Idempotent \(\implies\) Lille. For all \(x \in \mathbb{B}^n\), \(f(x)\) is the unique fixed point in \([x, f(x)] = T_f(x)\). Let \(y \in [x, f(x)]\), then \(f(y)\) is the unique fixed point in \(T_f(y) \subseteq T_f(x)\), hence \(f(y) = f(x)\). Thus, \([y, f(y)] = [x, f(x)]\) for all \(x \in \mathbb{B}^n\) and \(y \in [x, f(x)]\).
All the blue implications, that only hold for commutative networks, follow from the implication below.
(c) Commutative and Trapspace-FP \(\implies\) Lille. By Theorem 7.3, \(f\) is commutative and locally idempotent, i.e. \(f\) is Lille.
We now exhibit counterexamples to implications that are not displayed in Figure 5.
(a) Interval-UFP and Idempotent \(\nRightarrow\) Fixable.
(b) Interval-UFP and Idempotent \(\nRightarrow\) Locally Idempotent.
(c) Trapping and Interval-UFP \(\nRightarrow\) Idempotent.
(d) Globally Idempotent \(\nRightarrow\) Interval-UFP.
(e) Trapping and DPT \(\nRightarrow\) Idempotent.
(f) Trapping and Idempotent \(\nRightarrow\) Locally Idempotent.
(g) Trapping and Interval-UFP \(\nRightarrow\) Locally Idempotent.
\(\square\)
This paper tied together the topics of trapspaces of Boolean networks and of commutative networks. We have introduced trapping networks, that generalise commutative networks and are a normal form for the study of trapspaces of networks. We have also classified the collections of trapspaces and of principal trapspaces of networks. We have then focused on two particular classes of commutative networks, namely Marseille (bijective commutative) and Lille (idempotent commutative) networks. Those two classes are very well structured (for instance, one may extract over twenty different definitions of Lille networks in the paper) and highlight the broader structure of commutative and trapping networks at large.
We identify three main avenues for potential future work. First, one may want to develop the theory of trapping networks. In particular, one may classify networks of a particular class (e.g. linear, monotone, increasing, or with particular interaction graphs) that are trapping. Second, we have classified the collections of principal trapspaces as the so-called pre-principal collections of subcubes, which have a “simple” definition (i.e. \(\mathcal{Q} = \mu( \mathcal{Q} )\)). However, the computational complexity of deciding whether a collection of subcubes is pre-principal remains unknown. The same holds for collections of trapspaces, which are the pre-ideal collections of subcubes. Third, trapping networks are one way of generalising commutative networks; Table 1 naturally suggests other ways of doing so. It would be interesting to see how different generalisations of commutativity behave, both in terms of their dynamical properties and whether classifications such as in Figures 3 and 5 can be derived.
I would like to thank Loïc Paulevé and Sara Riva for developing work on trapspaces that led to the topic of this paper, and for fruitful discussions and advice throughout the preparation of this paper.