Abstract

Azuma et al.showed that a cactus-expandable Boolean network \(\Sigma\) is structurally oscillatory if and only if all the simple cycles of \(\Sigma\) contain an odd number of inhibiting edges. We show that we do not need the cactus-expandable condition. Namely, a strongly connected Boolean network \(\Sigma\) is structurally oscillatory if and only if all the simple cycles of \(\Sigma\) contain an odd number of inhibiting edges. Additionally, we provide a characterization of a structurally oscillatory Boolean network for the general case.

1 Introduction and Notation↩︎

1.1 Boolean dynamics↩︎

We call \(\{0, 1\}\) a Boolean domain, where \(0\) and \(1\) correspond to false and true respectively. We define operators \(\bar{\quad}\), \(\vee\), and \(\wedge\), that correspond to NOT, OR, and AND respectively. \[\bar{0} =1, \bar{1}=0;\] \[0 \vee 0 = 0, 0 \vee 1 = 1 \vee 0 = 1 \vee 1 = 1;\] \[0 \wedge 0 = 0 \wedge 1 = 1 \wedge 0 = 0, 1 \wedge 1 = 1.\]

We also endow \(\{0, 1\}\) with an order \(0<1\).

Fix a positive integer \(N\) and consider a function \(\varphi \colon \{0, 1\}^N \to \{0, 1\}, (x_1,\dots,x_N) \mapsto \varphi(x_1,\dots,x_N)\).

\(\varphi\) is said to be independent of \(x_i\), weakly increasing in \(x_i\), or weakly decreasing in \(x_i\) respectively if \[\varphi(x_1,\dots,x_{i-1},0,x_{i+1},\dots,x_N)= \varphi(x_1,\dots,x_{i-1},1,x_{i+1},\dots,x_N),\] \[\varphi(x_1,\dots,x_{i-1},0,x_{i+1},\dots,x_N)\leq \varphi(x_1,\dots,x_{i-1},1,x_{i+1},\dots,x_N),\] \[\varphi(x_1,\dots,x_{i-1},0,x_{i+1},\dots,x_N)\geq \varphi(x_1,\dots,x_{i-1},1,x_{i+1},\dots,x_N)\] for any \((x_1,\dots,x_{i-1},x_{i+1},\dots,x_N)\in\{0, 1\}^{N-1}\) respectively.

\(\varphi\) is said to be increasing in \(x_i\), or decreasing in \(x_i\) respectively if \(\varphi\) is not independent of \(x_i\) and is weakly increasing in \(x_i\), or weakly decreasing in \(x_i\) respectively.

We say that \(\varphi\) is monotone if for any \(i \in \{1,\dots,N\}\), \(\varphi\) is independent of \(x_i\), increasing in \(x_i\), or decreasing in \(x_i\) .

Suppose \(f \colon \{0, 1\}^N \to \{0, 1\}^N\) is a function. Then \(f\) defines a discrete dynamical system on \(\{0, 1\}^N\) by \(x(t+1):=f(x(t))\). In this paper, we only consider the case that for any \(j \in \{1,\dots,N\}\), \(f_j=\pi_j\circ f\) is monotone, where \(\pi_j\colon \{0, 1\}^N \to \{0, 1\}\) is the \(j\)-th projection. We call such a dynamical system a Boolean dynamical system.

We are now going to visualize Boolean dynamical systems by digraphs. Before that, we review the digraphs.

1.2 Digraphs↩︎

A digraph, or directed graph, is an ordered pair \(G = (V,A)\), where \(V\) is a finite set of vertices and \(A\) is a finite set of ordered pairs (called arcs) of vertices of \(V\), in other words, \(A\subset V \times V\). In this paper, we allow loops, i.e.\((v,v)\) can be an arc.

For an arc \(a=(v,w)\), we use the notation that \(s(a)=v\) and \(t(a)=w\). We also say that \(a\) is an arc from \(v\) to \(w\). For a vertex \(v \in V\), the indegree \(\delta^-(v)\) is the number of arcs to \(v\) and the outdegree \(\delta^+(v)\) is the number of arcs from \(v\).

A path of length \(n \geq 1\) from \(v\) to \(w\) is a sequence of \(n+1\) vertices \((v_0,v_1,\dots,v_{n-1},v_n)\) such that \(v_0=v\), \(v_n=w\) and \((v_{i-1},v_i)\in A\) for \(1 \leq i \leq n\). A path is called a simple path if \(x_0, \dots, x_{n-1}, x_n\) are distinct.

A cycle is a path with \(x_0 = x_n\). A cycle is called a simple cycle if \(x_0, \dots, x_{n-1}\) are distinct. Note that a simple cycle cannot be a simple path.

A digraph \(G=(V,A)\) is said to be strongly connected if for any vertices \(x,y \in V\) there exists a path from \(x\) to \(y\).

1.3 Boolean networks↩︎

Suppose a Boolean dynamical system is defined by a function \(f \colon \{0, 1\}^N \to \{0, 1\}^N\). The Boolean network \(\Sigma = (V, A^+, A^-)\) of \(f\) is constructed in the following way;

\(V = \{1, \dots, N \}\) is an \(N\)-point set.
\((V,A)\) is a digraph where \(A = A^+ \sqcup A^-\).
\((i,j) \not \in A\) if \(f_j\) is independent of \(x_i\).
\((i,j) \in A^+\) if \(f_j\) is increasing in \(x_i\).
\((i,j) \in A^-\) if \(f_j\) is decreasing in \(x_i\).

An element \((i,j) \in A^+\) is called an activating edge, and is denoted by \(i \to j\).

An element \((i,j) \in A^-\) is called an inhibiting edge, and is denoted by \(i \dashv j\).

Claim 1. If \(V = \{1, \dots, N \}\), \((V,A)\) is a digraph, and \(A = A^+ \sqcup A^-\) is a partition of \(A\), then there exists a function \(f \colon \{0, 1\}^N \to \{0, 1\}^N\) of which Boolean network is \((V, A^+, A^-)\).

On the other hand, even if \(f\) and \(f'\) have the same Boolean network \((V, A^+, A^-)\), \(f\) may differ from \(f'\).

Example 1. The following two distinct Boolean dynamical systems \(f\) and \(f'\) on \(\{0,1\}^4\) have the same Boolean network \(\Sigma\).

\[\begin{cases} f(x_1) = \bar{x_4} & {} \\ f(x_2) = x_1 & {} \\ f(x_3) = x_1 \vee \bar{x_2}& {} \\ f(x_4) = x_3 & \end{cases} , \quad \begin{cases} f'(x_1) = \bar{x_4} & {} \\ f'(x_2) = x_1 & {} \\ f'(x_3) = x_1 \wedge \bar{x_2}& {} \\ f'(x_4) = x_3 & \end{cases}\]

Figure 1: The Boolean network \Sigma in Example 1. — Figure 1: The Boolean network \(\Sigma\) in Example 1.

We say \(\Sigma = (V, A^+, A^-)\) is connected, strongly connected, … if the corresponding digraph \(G = (V, A^+ \sqcup A^-)\) connected, strongly connected, ….

2 The Strongly Connected Case↩︎

2.1 Characterization Theorem for Strongly Connected Case↩︎

A Boolean dynamical system \(f \colon \{0,1\}^N \to \{0,1\}^N\) is said to be oscillatory if it has no fixed point \(x \in \{0,1\}^N\). A Boolean network \(\Sigma\) is said to be structurally oscillatory if any Boolean dynamical system \(f\) represented by \(\Sigma\) is oscillatory.

Then, the main theorem in [1] can be restated in the following way:

Theorem 2. Suppose that \(\Sigma = (V, A^+, A^-)\) is a Boolean network and the digraph \(G = (V, A^+ \sqcup A^-)\) is cactus-expandable. Then \(\Sigma\) is structurally oscillatory if and only if any simple cycle of \(G\) has an odd number of inhibiting edges.

Definition of cactus-expandable digraphs can be found in [2], [1], and [3]. Here, we simply remark that it is stronger than being strongly connected.

Here is the main theorem of this section.

Theorem 3. Suppose that \(\Sigma = (V, A^+, A^-)\) is a Boolean network and the digraph \(G = (V, A^+ \sqcup A^-)\) is strongly connected. Then \(\Sigma\) is structurally oscillatory if and only if any simple cycle of \(G\) has an odd number of inhibiting edges.

2.2 Proof of the Theorem↩︎

We shall prove the contrapositive of Theorem 3.

2.2.1 If part↩︎

In this subsubsection, we shall prove the following proposition.

Proposition 4. If a Boolean dynamics \(f \colon \{0,1\}^N \to \{0,1\}^N\) has a fixed point \(\hat{x}\in\{0,1\}^N\), \(G = (V, A^+ \sqcup A^-)\) is a strongly connected digraph, and the Boolean network of \(f\) is \(\Sigma=(V, A^+, A^-)\), then \(G = (V, A^+ \sqcup A^-)\) has a simple cycle with an even number of inhibiting edges.

Definition 1. Fix a Boolean dynamics \(f \colon \{0,1\}^N \to \{0,1\}^N\) and a fixed point \(\hat{x}\in\{0,1\}^N\) of \(f\). Suppose Boolean network of \(f\) is \((V, A^+, A^-)\). Then partition the directed edge set \(A=A^+ \sqcup A^-\) into two colors. Take an arc \((i,j)\in A\).

If \((i,j) \in A^+\) and \(\hat{x}_i=\hat{x}_j\); or \((i,j) \in A^-\) and \(\hat{x}_i\neq \hat{x}_j\), then \((i,j)\) is called an admissible edge and colored green. If \((i,j) \in A^+\) and \(\hat{x}_i\neq\hat{x}_j\); or \((i,j) \in A^-\) and \(\hat{x}_i= \hat{x}_j\), then \((i,j)\) is called an inadmissible edge and colored red.

In other words, \(0 \to 0\), \(1 \to 1\), \(0 \dashv 1\), \(1 \dashv 0\) are admissible edges, and \(0 \to 1\), \(1 \to 0\), \(0 \dashv 0\), \(1 \dashv 1\) are inadmissible edges.

Lemma 1. Fix a Boolean dynamics \(f \colon \{0,1\}^N \to \{0,1\}^N\) and a fixed point \(\hat{x}\in\{0,1\}^N\) of \(f\). If the Boolean network \(\Sigma = (V,A^+,A^-)\) of \(f\) is strongly connected, then each vertex \(v_j \in V\) has at least one incoming admissible edge.

Proof. We prove the lemma by contradiction. Without loss of generality, suppose \(\hat{x}_j=1\). We assume that all incoming edges to \(v_j\) are inadmissible. Let \(I^+:=\{i \mid \text{(i,j) is an activating edge}\}\) and \(I^-:=\{i \mid \text{(i,j) is an inhibiting edge}\}\).

Since \(\hat{x}\) is a fixed point of \(f\), \(f_j(\hat{x})=\hat{x}_j=1\). By definition, \(\hat{x}_i=0\) if \(i\in I^+\) and \(\hat{x}_i=1\) if \(i\in I^-\). On the other hand, the function \(f_j(x_1,\dots,x_N)\) is increasing in \(x_i\) if \(i\in I^+\), decreasing in \(x_i\) if \(i\in I^-\), and independent of \(x_i\) if \(i \not\in I^+ \sqcup I^-\). Therefore, \(f_j(x_1,\dots,x_N)=1\) for any \((x_1,\dots,x_N)\), so it is a constant function; this is a contradiction.

We can treat the case \(\hat{x}_j=0\) in a similar way. ◻

Proof of the proposition 4. Take an arbitrary node \(v_j \in V\) and set \(j_0=j\). \(v_{j_0}\) has at least one incoming admissible edge \((j_1,j_0)\). Inductively, suppose \((j_{i+1},j_i)\) is an admissible edge for \(i=1,2,\dots\). Since \(V\) is a finite set, there exist \(n_0\) and \(n_1\) so that \(n_0 < n_1\), \(j_{n_0} = j_{n_1}\), and \((j_{n_1}, j_{n_1-1}, \dots, j_{n_0+1}, j_{n_0})\) is a simple cycle of \(G\) consisting of admissible edges. Since this cycle is composed of admissible edges, the number of inhibiting edges should be even because of the parity. ◻

2.2.2 Only If part↩︎

In this subsubsection, we shall prove the other way.

Proposition 5. If \(G = (V, A^+ \sqcup A^-)\) is strongly connected and has a simple cycle with an even number of inhibiting edges, then there exists a function \(f \colon \{0,1\}^N \to \{0,1\}^N\) with a fixed point \(\hat{x}\in\{0,1\}^N\), such that the Boolean network of \(f\) is \((V, A^+, A^-)\).

Before proving the proposition, we will define some notation of a digraph. The notion of an out-tree or (an arborescence) is defined by Deo [4].

Definition 2. A digraph \(T\) is said to be an out-tree (or an arborescence) if

\(T\) is a tree as a non-directed graph.
\(T\) has a unique vertex \(r\) of zero in-degree.

This node \(r\) is called the root of the out-tree. An example of an out-tree is shown in Fig 2.

Figure 2: An out-tree T with a root r. — Figure 2: An out-tree \(T\) with a root \(r\).

Definition 3. Suppose that \(C\), \(T_1\), …, \(T_k\) are subdigraphs of a digraph \(G\) so that \(C\) is a simple cycle and \(T_i\) is an out-tree with a root \(r_i\). We also assume that \(C \cap T_i = \{r_i\}\) and \(T_i \cap T_j = \emptyset\) for \(i \neq j\). In such a case, we call a subdigraph \(B := C \cup T_1 \cup \cdots \cup T_k\) a bonsai on \(C\).

Figure 3: A bonsai on a simple cycle C. — Figure 3: A bonsai on a simple cycle \(C\).

See Figure 3 for an example of bonsai. We note that every vertex in a bonsai has an incoming edge of a bonsai. Here is an important lemma for a bonsai.

Lemma 2. (Existence of a Spanning Bonsai) Suppose \(C\) is a simple cycle in a strongly connected digraph \(G\). Then there exists a bonsai \(B\) on \(C\) that includes all the vertices of \(G\). Such a bonsai is called a spanning bonsai in \(G\).

Proof. Suppose \(\mathcal{B}(G,C)\) is the set of all bonsais on \(C\) in \(G\). Since \(\mathcal{B}(G,C)\) is a finite set, we can take a maximal element \(B_{\mathrm{max}}\) among \(\mathcal{B}(G,C)\) with respect to inclusion. Then \(B_{\mathrm{max}}\) is a spanning bonsai. If otherwise, take vertices \(y \not \in B_{\mathrm{max}}\) and \(x \in B_{\mathrm{max}}\). Since \(G\) is strongly connected, there exists a simple path \((x=x_0, x_1,\dots,x_n=y)\) from \(x\) to \(y\). Set \(i:= \max\{j \mid x_j \in B_{\mathrm{max}}\). Then \(B_{\mathrm{max}} \cup (x_i,\dots,x_n)\) is also a bonsai on \(C\). That contradicts the fact that \(B_{\mathrm{max}}\) is maximal. ◻

Now we can prove our proposition.

Proof of the proposition 5. Suppose \(G = (V, A^+ \sqcup A^-)\) is strongly connected and \(C\) is a simple cycle with an even number of inhibiting edges, Then, from the lemma above, there is a spanning bonsai \(B \subset \mathcal{B}(G,C)\).

We set a candidate for a fixed point \(\hat{x}\) so that every edge of \(B\) is admissible with respect to \(\hat{x}\). This is possible since \(B\) has only one cycle \(C\), which has an even number of inhibiting edges.

Then we shall construct \(f\) so that \(f(\hat{x})=\hat{x}\) and \(f\) is compatible with \(\Sigma=(V, A^+, A^-)\). This can be done quite simply. The main idea is if \(\hat{x}_j=0\) then construct \(f_j\) by AND, and if \(\hat{x}_j=1\) then construct \(f_j\) by OR.

To be precise, if \(\hat{x}_j=0\) then \[f_j(x) = \left( \bigwedge_{(i,j)\in A^+} x_i \right) \wedge \left( \bigwedge_{(i,j)\in A^-} \bar{x_i} \right),\] and if \(\hat{x}_j=1\) then \[f_j(x) := \left( \bigvee_{(i,j)\in A^+} x_i \right) \vee \left( \bigvee_{(i,j)\in A^-} \bar{x_i} \right).\] Then \(f(\hat{x}):=\hat{x}\) and \(f\) is compatible with \(\Sigma=(V, A^+, A^-)\). Since \(B\) is a spanning bonsai, every vertex has at least one incoming admissible edge; this \(f\) fixes \(\hat{x}\). ◻

Theorem 3 follows from propositions 4 and 5.

3 General case↩︎

Now we are going to study the case where \(\Sigma\) is not strongly connected. Note that if \(j \in V\) has no incoming edge, then \(f_j\) does not depend on anything, so it is a constant function.

The main idea is the following. See Figure 4. (a) is structurally oscillatory because it is strongly connected and its unique simple cycle has an odd number of inhibiting edges. (b) is not structurally oscillatory because it is strongly connected and has a simple cycle with an even number of inhibiting edges. (c) is structurally oscillatory, because the outward edge does not affect the dynamical system. However, (d) is not structurally oscillatory. This means that inward edges do affect the dynamical system. So the idea is that we should focus on the most upstream region.

Figure 4: Examples illustrating structural oscillatority.

3.1 Preorder and Strongly Connected Component↩︎

We define a binary relation \(\precsim\) on \(V\) by \(x \precsim y\) if there exist a directed path from \(x\) to \(y\) or \(x=y\). Then, \(\precsim\) is a preorder; that is, it satisfies:

Reflexivity: \(x \precsim x\) for all \(x \in V\).
Transitivity: If \(x \precsim y\) and \(y \precsim z\) then \(x \precsim z\) for all \(x,y,z \in V\).

We write \(x \sim y\) if \(x \precsim y\) and \(y \precsim x\). Then \(\sim\) is an equivalence relation. Suppose \(V/\sim \, = \{V_1, \dots, V_l\}\). Take \(\Sigma_i=(V_i,A_i^+,A_i^-)\) and \(G_i=(V_i,A_i)\) as Boolean full subnetworks and full subdigraphs; that is, \[A_i^+ := \{ (x,y) \mid \text{x,y \in V_i and (x,y)\in A^+} \},\] \[A_i^- := \{ (x,y) \mid \text{x,y \in V_i and (x,y)\in A^-} \},\] \[A_i := \{ (x,y) \mid \text{x,y \in V_i and (x,y)\in A} \} = A_i^+ \sqcup A_i^-.\]

Each subdigraph \(G_i\) is called a strongly connected component of \(G\). \(G_i\) is either a single vertex without a loop, or a maximal strongly connected subdigraph of \(G\).

The preorder \(\precsim\) on \(V\) induces a partial order \(\leq\) on \(V/\sim\). Note that \(V_i \leq V_j\) if and only if for any \(x \in V_i\) and \(y \in V_j\) there exists a directed path from \(x\) to \(y\), or \(V_i=V_j\) is a single vertex without a loop.

We also induce the same order on \(\{\Sigma_1, \dots, \Sigma_l \}\) and \(\{G_1, \dots, G_l\}\), that is, \(V_i \leq V_j \Leftrightarrow \Sigma_i \leq \Sigma_j \Leftrightarrow G_i \leq G_j\).

Define \(\mathcal{S}_{\mathrm{min}}\) to be the set of all minimal elements of \((\{\Sigma_1, \dots, \Sigma_l \}, \leq)\), and \(I_{\mathrm{min}}\) is the index set of \(\mathcal{S}_{\mathrm{min}}\), i.e. \[I_{\mathrm{min}}:= \{i \in \{1,\dots,l\} \mid \Sigma_i \in \mathcal{S}_{\mathrm{min}} \}\]

Now we can state the characterization theorem for the general case:

Theorem 6. \(\Sigma\) is structurally oscillatory if and only if at least one of \(\Sigma_i \in \mathcal{S}_{\mathrm{min}}\) is structurally oscillatory.

Since \(\Sigma_i\) is either strongly connected or a single vertex, theorems 3 and 6 give the perfect criterion for structurally oscillatory.

Proof of theorem 6. If \(\Sigma_i \in \mathcal{S}_{\mathrm{min}}\) is structurally oscillatory, then \(f \mid _{ \{0,1\}^{V_i}}\) cannot have a fixed point, so as \(f\).

Suppose that all \(\Sigma_i \in \mathcal{S}_{\mathrm{min}}\) are not structurally oscillatory. Then, each \(\Sigma_i\) either is a single point without a loop, or has a bonsai \(B_i\) on a simple cycle \(C_i\) with an even number of inhibiting edges.

Then consider a set \(\mathcal{F}=\{ \check{B}_1,\dots,\check{B}_l\}\), where \(\check {B_i}\) is an out-tree rooted on the single vertex of \(\Sigma_i\) if \(\Sigma_i\) is a single point without loop, otherwise \(\check {B_i}\) is a bonsai on \(C_i\) and \(\check {B_i} \supset B_i\), and \(\check{B}_1,\dots,\check{B}_l\) are disjoint. Then the maximal element among them, in a sense of inclusion, covers every vertex of \(\Sigma\), therefore we can create a fixed point \(\hat{x}\) and function \(f\) in the same way as Proof of the proposition 5. ◻

Acknowledgement↩︎

I would like to express my gratitude for the meaningful discussions with Shun-ichi Azuma. Additionally, I appreciate Ryosuke Iritani for his contributions and support.

References↩︎

[1]

Shun-ichi Azuma, Takahiro Yoshida, Toshiharu Sugie; Structural Oscillatority Analysis of Boolean Networks IEEE Transactions on Control of Network Systems, pp 464–473, 2019 June.

[2]

Shun-ichi Azuma, Toshimitsu Kure, Takahiro Yoshida, and Toshiharu Sugie; Cactus-Expandable Graphs, IEEE Transactions on Control of Network Systems, pp 775–788, 2019 June.

[3]

Hiroki Kodama; Characterization of cactus-expandable digraphs via doubly bidirectionally connected pairs, preprint 2023, https://arxiv.org/abs/2312.17327.

[4]

Narsingh Deo; Graph Theory with Applications to Engineering and Computer Science, Englewood, New Jersey: Prentice-Hall, 1974, ISBN 0-13-363473-6.

Structural Oscillatority Criterion of Boolean Networks