Convergence of monotone boolean network in the worst case

Question

I'm looking for (upper bound) convergence of increasing monotone boolean network (network composed only with OR, AND, identity ($f_i(x)=x_j$) functions) in asynchronous updating mode. It means that if we make the graph which represents the transitions (asynchronous transition state =ATS), it only exists an arc between two configurations which have a Hamming distance equal to one (i.e one component can change. The Hamming distance is the number of difference between two state. For example the hamming distance between 001 and 010 is 2 because two components are differents).

Moreover we can notice that the graph representing the derivatives is acyclic by problem definition. The graph of derivative called interaction graph G=(V,E) where V= {1,..n} and it exists an edge between i and j if the discrete derivative is not null. The value of the arc is the derivative sign see example below.

By F.Robert conjecture (1980) we know that if the derivative graph is acyclic then the asynchronous network state too and the boolean network have only one fixed point (i.e f(x) = x).

---

Definition monotone function

We know that for a monotone function in a boolean network, $\forall x,y \in \mathbb{B}^n,$ if $ x \leq y \implies f(x) \leq f(y)$. Further all derivative are positive.

---

Definition discrete derivative:

Let f be a network on V and two components i,j $\in$ V (where V={1,...,n}). The discrete derivative of $f_i$ with respect to j is the function $f_{ij}$ from $\mathbb{B}^V$ to {-1,0,1} defined by:

$\forall x \in \mathbb{B}^V, f_{ij}(x)=f_i(x^{j1}-f_i(x^{j0}).$

<=>$ f_{ij}(x)=f_i(x_1,x_2,..,x_j(=1)...,x_n)-f_i(x_1,x_2,..,x_j(=0)...,x_n))$

---

For instance let $N$ the following boolean network, which is increasing monotonous.

$$N=\begin{cases} f_1(x) = x_3\\ f_2(x) = x_1 \vee x_3\\ f_3(x) = 1 \\ \end{cases}$$

Produce this transition array

$$\begin{array}{ccc|ccc} x_1 & x_2 & x_3 & f(x_1) & f(x_2) & f(x_3)\\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \end{array}$$

---

In the asynchronous transition state graph there exists an edge from $(0 , 0 , 0)$ to $(0 , 0 , 1)$. But this transition $(1 , 0 , 0)\to (0 , 1 , 1)$ leads to $2$ transitions $(1 , 0 , 0)\to (0 , 0 , 0) ,\quad (1 , 1 , 0)\to (0 , 1 , 1)$ and $(1 , 0 , 1) \to (0 , 1 , 1)$.

---

Another example: the following figure is the asynchronous transition graph of:

$$N=\begin{cases} f_1(x) = 1\\f_2(x) = x_1 \\ \end{cases}$$

And it's interaction graph (which represent all derivatives)

In this network the size of the longest path is 3 : (01)$\to$(00)$\to$(10)$\to$(11)

---

To recall, I search the longest path in asynchronous boolean network (ATS)

I tried to prove that the max path in such a network is $n^2$. My idea was simple : we prove that if we fix a state (e.g, $x_1 = 1$) there remain only $n$ accessible states, otherwise if we add another arc in the path there exists a cycle. But this idea has a problem: how can one prove that the path is maximum?

Answer 1

I will construct a network that contains a simple path of length $2^{n/4}$ (at least) for any $n$ divisible by $4$. (It's possible that there are better lowerbounds like $2^{n/2}$, just more complicated.)

• We will use $4$ types of variables, call them $a_i$, $b_i$, $c_i$ and $d_i$ (this is just to know what is going on, normally all would be called $x_{something}$, e.g. $x_{4i+3}$ for $d_i$).

• $a_i$'s will simulate a binary counter that goes from $0$ to $2^{n/4}-1$.

• $b_i$'s will be negations of $a_i$'s, i.e. $b_i = \neg a_i$. That property will not be calculated, but will be maintained as an invariant between big-steps.
• $c_i$'s and $d_i$'s will be copies of $a_i$'s and $b_i$'s for simplicity.
• Each big step will be a next increment of the counter. Between big steps the Hamming distance will differ by at least $1$ (because of the counter).
• Each big step will consists of multiple small steps, some of them of Hamming distance zero. This non-significant small steps should be omitted in the final path. The rest should just be kept to maintain steps of Hamming distance one. Therefore, the length of final path will be somewhere between $2^{n/4}$ and $n\cdot2^{n/4}$.

We start with $a_i = c_i = 0$ and $b_i = d_i = 1$. Then we update all $a_i$'s and $b_i$'s based on $c_i$'s and $d_i$'s, and then we copy the result back into $c_i$'s and $d_i$'s. In other words \begin{align} f_{c_i}(a\ldots,b\ldots,c\ldots,d\ldots) &= a_i \\ f_{d_i}(a\ldots,b\ldots,c\ldots,d\ldots) &= b_i \end{align}

Now for the important part, let's construct $f_{a_i}$ and $f_{b_i}$.

\begin{align} &f_{\color{red}{a}_\color{magenta}{i}}(a\ldots,b\ldots,c\ldots,d\ldots) = \\ &\quad\bigvee_{0 \leq k < 2^{n/4},\ \operatorname{bin}_\color{magenta}{i}(k+1) = \color{red}{1}}\quad\left(\bigwedge_{0\leq j < n/4,\ \operatorname{bin}_j(k) = \color{blue}{1}}\color{blue}{c}_j\right)\land\left(\bigwedge_{0\leq j < n/4,\ \operatorname{bin}_j(k) = \color{blue}{0}}\color{blue}{d}_j\right) \\ \\ &f_{\color{red}{b}_\color{magenta}{i}}(a\ldots,b\ldots,c\ldots,d\ldots) = \\ &\quad\bigvee_{0 \leq k < 2^{n/4},\ \operatorname{bin}_\color{magenta}{i}(k+1) = \color{red}{0}}\quad\left(\bigwedge_{0\leq j < n/4,\ \operatorname{bin}_j(k) = \color{blue}{1}}\color{blue}{c}_j\right)\land\left(\bigwedge_{0\leq j < n/4,\ \operatorname{bin}_j(k) = \color{blue}{0}}\color{blue}{d}_j\right) \end{align} where $\operatorname{bin}_\alpha(\beta)$ is the digit of binary expansion of $\beta$ corresponding to $2^\alpha$ component (i.e. $(\alpha-1)$-th from the back).

Big step consists of updates for all $a_i$'s, then for all $b_i$'s, then $c_i$'s and finally all $d_i$'s.

Observe that this construction contains a cycle because the counter overflows (so in the worst case you could loop infinitely)! For example for $n = 4$ we have an $1$-bit counter (indices of $a_1$, $b_1$, $c_1$ and $d_1$ were left out):

\begin{align} f_a(a,b,c,d) = d \\ f_b(a,b,c,d) = c \\ f_c(a,b,c,d) = a \\ f_d(a,b,c,d) = b \\ \end{align}

Consider the sequence:

\begin{align} &\text{ the counter value is 0}\\ (0,1,0,1) & \xrightarrow{\text{ update } a}\\ (1,1,0,1) & \xrightarrow{\text{ update } b}\\ (1,0,0,1) & \xrightarrow{\text{ update } c}\\ (1,0,1,1) & \xrightarrow{\text{ update } d}\\ &\text{ the first big step finished, the counter value is 1}\\ (1,0,1,0) & \xrightarrow{\text{ update } a}\\ (0,0,1,0) & \xrightarrow{\text{ update } b}\\ (0,1,1,0) & \xrightarrow{\text{ update } c}\\ (0,1,0,0) & \xrightarrow{\text{ update } d}\\ &\text{ the second big step finished}\\ &\text{ the counter overflows, its value is again 0}\\ (0,1,0,1) & \quad\text{ cycle} \end{align}

I hope this helps $\ddot\smile$

Edit:

You afterwards added an assumption that the dependency graph has to be acyclic. It's possible to generate a path of length $2\cdot 2^{n/2}$ for such network. The example is more complicated than the one above and it is a merge of three ideas:

• the above example, i.e. the counter and treatment of negatives,
• Gray codes,
• update pattern based on A007814, namely: $$ a_0,b_0,a_1,b_1,a_0,b_0,a_2,b_2,a_0,b_0,a_1,b_1,a_0,b_0,a_3,b_3,\ldots $$

I don't have enough patience to write down the general formulae, so I will provide an example for $n = 8$, that is, corresponding to $4$-bit Gray codes. Note that the $a_i$ depends on $a_j$'s and $b_j$'s only for $j > i$, so the dependency graph is acyclic. I hope that you will be able to reconstruct the general case based on my example:

aaaa bbbb
3210 3210

0000 1111
0001 1110
0011 1100
0010 1101
0110 1001
0111 1000
0101 1010
0100 1011
1100 0011
1101 0010
1111 0000
1110 0001
1010 0101
1011 0100
1001 0110
1000 0111

\begin{align} f_{a_0} &= (b_3\land{}b_2\land{}b_1) \lor (b_3\land{}a_2\land{}a_1) \lor (a_3\land{}a_2\land{}b_1) \lor (a_3\land{}b_2\land{}a_1) \\ f_{a_1} &= (b_3\land{}b_2) \lor (a_3\land{}a_2) \\ f_{a_2} &= b_3 \\ f_{a_3} &= 1 \\ f_{b_0} &= (b_3\land{}b_2\land{}a_1) \lor (b_3\land{}a_2\land{}b_1) \lor (a_3\land{}a_2\land{}a_1) \lor (a_3\land{}b_2\land{}b_1) \\ f_{b_1} &= (b_3\land{}a_2) \lor (a_3\land{}b_2) \\ f_{b_2} &= a_3 \\ f_{b_3} &= 0 \end{align}

The way to construct $f_{a_0}$ is that $3$-bit Gray codes are 000, 001, 011, 010, 110, 111, 101, 100 and codes on odd positions give you 000, 011, 110, 101, which is precisely what you need; codes on even position will form $f_{b_0}$. Another way to look at it, is that the components of $f_{a_0}$ have even number of $a_i$'s.

Here is a simple Ruby snippet that demonstrates the path (you can try it here):

fa = [
  lambda{|a,b| b[3]*b[2]*b[1] + b[3]*a[2]*a[1] + 
               a[3]*a[2]*b[1] + a[3]*b[2]*a[1]},
  lambda{|a,b| b[3]*b[2] + a[3]*a[2]},
  lambda{|a,b| b[3]},
  lambda{|a,b| 1}
  ]
fb = [
  lambda{|a,b| b[3]*b[2]*a[1] + b[3]*a[2]*b[1] + 
               a[3]*a[2]*a[1] + a[3]*b[2]*b[1]},
  lambda{|a,b| b[3]*a[2] + a[3]*b[2]},
  lambda{|a,b| a[3]},
  lambda{|a,b| 0}
  ]
a = [0,0,0,0]
b = [1,1,1,1]
[0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0].each do |ii|
  a[ii] = fa[ii][a,b]
  b[ii] = fb[ii][a,b]
  print a, "\n"
end