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$.

Improve this question
$\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. ♦
    Mar 5, 2022 at 1:16
  • $\begingroup$ The more common term is antichain. $\endgroup$
    – Yuval Filmus
    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$
    – Raúl Astete
    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
    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$
    – Yuval Filmus
    Mar 6, 2022 at 17:41

0

Reset to default

Your Answer

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