1
$\begingroup$

First some context:

  1. A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself.

  2. The dynamical behavior of a Boolean Network $f$ is given by the iteration of the function itself, i.e. for all $x(t)\in \{0,1\}^n$, $x(t+1) = f(x(t))$. Since the set $\{0,1\}^n$ is finite, this can be represented by a finite graph $G_I(f)$, what is usually called the "dynamic" of the Boolean network. A directed cycle of $G_I(f)$ that involves more than one vertex is called a limit cycle.

  3. Given a Boolean Network $f:\{0,1\}^n\to\{0,1\}^n$, $f(x) = (f_1(x),\ldots,f_n(x))$, we define the interaction graph $G(f)$ whose vertex are $\{1,\ldots,n\}$ and there is an arc from $i$ to $j$ iff $f_j$ depends on the variable in the component $i$.

  4. Given two Boolean vectors $x$ and $y$, we say that $x\leq y$ if $x_i\leq y_i$ for all $i = 1,\ldots,n$. A Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ is monotonic if for all $x$, $y \in\{0,1\}^n$, if $x\leq y$ then $f(x)\leq f(y)$.

  5. We say that a Boolean Network $f$ is bijective if $f$ is a bijective function, i.e. $f$ is a bijection from $\{0,1\}^n$ to $\{0,1\}^n$.

I am trying to understand the relationship between lengths of limit cycles and cycles on the interaction graph of a Boolean Network. I know that bijective monotonic Boolean networks have interaction graphs composed of disjoint directed cycles, and that every limit cycle (directed cycle on the dynamic of the network) is a sequence of noncomparable Boolean vectors. The first natural question that i want to answer is: Given $S$ a sequence of noncomparable Boolean vectors, does there exists a bijective monotonic Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ such that $S$ is a limit cycle of $f$? (That's not the question of the post)

In that sense, it will be useful to have an algorithm to generate a sequence of noncomparable Boolean vectors. Does there exists an algorithm for that?

Thanks in advance.

PS: Given two Boolean vectors $x = (x_1,\ldots,x_n)$ and $y = (y_1,\ldots,y_n)$, we say that $x$ and $y$ are $\textbf{non-comparable}$ if it's not true that $x_i\leq y_i$ (or $x_i\geq y_i$) for all $i = 1,\ldots n$.

$\endgroup$
6
  • $\begingroup$ Can you give a self-contained definition of your terms? What is a Boolean network? What is a bijective monotonic Boolean network? What is the interaction network of a Boolean network? What is a "limit cycle"? What is the "dynamic" of a network? Please ask only one question per post. I see two questions in your post. You can ask them separately, in two separate posts. $\endgroup$
    – D.W.
    Commented Mar 5, 2022 at 1:16
  • $\begingroup$ The more common term is antichain. $\endgroup$ Commented Mar 5, 2022 at 7:57
  • $\begingroup$ I've made some changes in the post. If it's possible i want to find a determinstic algorithm that generates an antichain of Boolean vectors. It will be useful for studying the patterns behind the connection between the two graphs associated with the Boolean network. I apologize if I don't use the standard nomenclature, since English is not my first language. $\endgroup$ Commented Mar 6, 2022 at 14:59
  • $\begingroup$ You state you want to generate a sequence of noncomparable Boolean vectors. But that is trivial if no constraints are given (for example, take the empty sequence). I guess you want something else? Perhaps you want to enumerate all such antichains? i.e. enumerate M(n) such sequences. $\endgroup$
    – pcpthm
    Commented Mar 6, 2022 at 15:35
  • 2
    $\begingroup$ All vectors of weight $w$ form an antichain for all $w$. Sperner proved that taking $w = \lfloor n/2 \rfloor$ gives the largest possible antichain. $\endgroup$ Commented Mar 6, 2022 at 17:41

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.