# Conditions for cyclic attractors for a class of discrete n-dimensional repressilators

Honglu Sun, Maxime Folschette, Morgan Magnin, Elisa Tonello

► To cite this version:

Honglu Sun, Maxime Folschette, Morgan Magnin, Elisa Tonello. Conditions for cyclic attractors for a class of discrete n-dimensional repressilators. The 31st International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2025), Sara Riva; Adrien Richard, Jun 2025, Villeneuve-d'Ascq, France. pp.139-153, 10.1007/978-3-032-01570-9_10. hal-05236106

HAL Id: hal-05236106

https://hal.science/hal-05236106v1

Submitted on 2 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Conditions for cyclic attractors for a class of
discrete *n*-dimensional repressilators

Honglu Sun¹[0000-0002-8265-0984], Maxime Folschette²[0000-0002-3727-2320],
Morgan Magnin¹[0000-0001-5443-0506], and Elisa Tonello³[0000-0002-5182-4216]

¹ Nantes Université, École Centrale Nantes, CNRS, LS2N, UMR 6004, F-44000 Nantes, France

² Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRStAL, F-59000 Lille, France
Maxime.Folschette@centralelille.fr

³ Department of Mathematics and Computer Science, Freie Universität Berlin

**Abstract.** Repressilators are biological regulatory networks in which components interact only in terms of negative influences. They are of interest in biology, since their oscillatory behavior can inform the design of gene therapies. Although sustained oscillations are ensured in 3-dimensional repressilators, that is, in systems made of 3 genes, they do not always appear in higher dimensions, as their occurrence depends on the topology of the network and on the chosen parameters. Here we focus on discrete models, where the presence of at least one cyclic attractor is required for sustained oscillations. Even in a discrete framework, enumerating and simulating all possible models can quickly become computationally infeasible. In this paper, we provide a sufficient condition for the presence of sustained oscillations for a class of repressilators, based on the structure of their influence graphs. The condition applies in any dimension and independently of the parameters, that is, threshold labeling of the edges. We also study the coexistence of cyclic attractors and fixed points in dimension 4.

**Keywords:** Discrete regulatory networks · Interaction graph · Repressilators · Static analysis · Attractors.

# 1 Introduction

Gene expression has generally two major steps: transcription, that generates mRNA from genes, and translation, that generates proteins from mRNA. A generated protein can be structural (giving it a particular structural property) or be an enzyme (catalyzing a certain reaction). Additionally, it can also serve to activate or inhibit other genes. These regulations (activation or inhibition) between genes give rise to *gene regulatory networks*, which play a key role in various cellular processes and pathways [Kauffman, 1969, Thomas, 1973, de Jong, 2002].

One major challenge associated to gene regulatory networks is the analysis of their dynamical properties. In the literature, various classes of these properties have been studied, such as the existence of oscillations or fixed points
[Melkman et al., 2010, Akutsu et al., 2012, Comet et al., 2013], state reachability [Batt et al., 2008, Paulevé et al., 2012, Mendes et al., 2018], or more complex properties described by temporal logic [Bernot et al., 2004]. Identifying the dynamical properties of gene regulatory networks enables the correction of inaccurate models, the prediction of a system's behavior, and even the discovery of new strategies for regulating specific parts of the network.

However, studying such properties often requires to exhaustively compute the dynamics of the model, either completely or partially. This computation can be very time-costly since it usually has an exponential complexity in the size of the model, which is typically determined by the number of genes. Several techniques exist to speed up the process (such as model reduction, see for instance [Naldi et al., 2011]), but these do not reduce the inherent complexity of the problem. Thus, when possible, relying on static analysis is an interesting alternative. Static analysis consists in computing dynamical properties based only on the topology of the model, thus avoiding the exhaustive computation of the dynamics. This results in a drastic decrease in computational complexity although, so far, ad hoc techniques or properties must be found for each problem addressed [Paulevé and Richard, 2012, Gadouleau, 2020].

In the literature, different modeling frameworks have been applied to model gene regulatory networks, mainly including probabilistic, continuous, discrete or hybrid approaches [de Jong, 2002]. This work uses Thomas' discrete modeling framework [Thomas, 1973, Thomas, 1991], where the continuous expressions of the genes are abstracted by an integer vector called a *state*, which describes the discrete expression levels of genes, so that the dynamics of the system can be represented by a state transition graph. One major advantage of using discrete modeling is its simplicity in implementation and analysis. Based on this discrete modeling framework, one can describe the dynamical properties in terms of the existence of different attractors (fixed points and cyclic attractors) in the state transition graph. The significance of attractors lies in their representation of the system's long-term behavior, which typically corresponds to the phenotype of a living organism.

This study considers the problem of determining to what extent the presence of a certain type of attractors (fixed points, cyclic attractors, or both) which generally depend on both the structure of the regulations and the specific modeling formalism, can be inferred solely from the topology of the *interaction graph*. The interaction graph of a gene regulatory network is a directed graph where the vertices represent the genes and the arcs represent the regulations between genes. We study a class of gene regulatory networks, called *n*-dimensional replicators, which are *n*-dimensional networks with only inhibitions between genes. The 3-dimensional repressilator, consisting of a single negative feedback loop, was widely studied in synthetic biology because it can generate synthetic oscillations [Potvin-Trottier et al., 2016, Elowitz and Leibler, 2000]. However, adding more genes to this network tends to improve the controllability of this model [Page, 2019, Perez-Carrasco et al., 2018, Goh et al., 2008]. In [Sun et al., 2023], a sufficient and necessary condition for the existence of a cyclic attractor in the
particular case of 4-dimensional repressilators was discovered by machine learn-
ing models. Here we describe conditions for the existence of fixed points or cyclic
attractors in $n$-dimensional repressilators without resorting to machine learning
techniques. The first contribution is the formulation of a sufficient and necessary
condition for the existence of fixed points in $n$-dimensional repressilators, which
also leads to a sufficient condition for the existence of cyclic attractors. Note that
this result has already been reported in [Richard and Ruet, 2013, Proposition 4]
for a subclass of Boolean models. We then state a sufficient condition for the
coexistence of fixed points and cyclic attractors in $n$-dimensional repressilators.
Finally, we prove that this sufficient condition is also a necessary condition in
the case of 4-dimensional repressilators, which is compatible with the results in
[Sun et al., 2023].

## 2 Definitions

In this work, we consider a subset of multi-valued networks, also often called
Thomas models [Thomas, 1973; Thomas, 1991]. Indeed, we consider discrete net-
works on $n$ species with interaction graphs admitting *inhibition interactions only*,
and call these interaction graphs *repressilator* interaction graphs. We consider
only repressilators without self-loops, and with the following dynamical rule: one
in-neighbor is sufficient to decrease the target value. This means in particular
that the asynchronous dynamics is uniquely defined by the interaction graph and
the threshold assignment, that is, the labeling of the arcs indicating at which
expression level the source gene starts expressing its influence on the target gene.
The same assumption was also made in [Sun et al., 2023]. However, contrary to
the other assumptions of the same article, here we do not assume that every
vertex is the regulator of at least one other vertex and that a different threshold
exists for each target, and we do not limit the networks to 4 components.

To simplify the discussion, we assume, without loss of generality, that the
directed graph underlying the interaction graph is connected. If this condition is
not satisfied, the asynchronous dynamics associated to the interaction graph can
be described as the Cartesian product of the asynchronous dynamics associated
to each connected component. In particular, the dynamics admits a cyclic at-
tractor if and only if any of the dynamics associated to a connected component
admits a cyclic attractor.

**Definition 1.** For a repressilator interaction graph $G$, let $V = \{0, \dots, n-1\}$ be the set of vertices, and $E$ the set of directed edges. A maximum level assignment $m: V \to N \setminus \{0\}$ associates a strictly positive maximum level to each vertex in $G$. For simplicity, for each vertex $i \in V$, we write $m_i$ instead of $m(i)$. Thus, $X = \{0, \dots, m_0\} \times \dots \times \{0, \dots, m_{n-1}\}$ is the state space of the dynamics associated to $G$.

For convenience, in the rest of this paper, and since we model only negative
regulations, if $i, j \in V$ are two vertices such that there is an edge $(i, j) \in E$, we
say that *i inhibits* *j*, *i* is called an *inhibitor* of *j*, and the edge $(i, j)$ is called an
**inhibition.** Recall that the sign of a path in an interaction graph is the product of the sign of its arcs. Hence, in a repressilator graph, a cycle is negative if and only if it contains an odd number of arcs.

**Definition 2.** Let $G$ be an interaction graph and $m$ a maximum level assignment. A threshold assignment $t: E \to \mathbb{N}$ associates a threshold to each edge in $G$ so that, for each edge $(i, j) \in E$, $0 < t(i, j) \le m_i$.

Let $d(x, y)$ denote the Hamming distance between $x, y \in X$. Moreover, if $x \in X$ and $i \in V$, $x_i$ denotes the $i^{th}$ component of state $x$.

**Definition 3.** Given a repressilator interaction graph $G$, a maximum level assignment $m$ and a threshold assignment $t$, $\text{AD}(G, m, t)$ is the associated asynchronous state transition graph, also called asynchronous dynamics, defined as follows: for $i \in V$ and $x, y \in X$,

- there is a transition from $x$ to $y$ with $d(x, y) = 1$ and $y_i = x_i + 1$ if and only if $x_i < m_i$ and $x_j < t(j, i)$ for all inhibitors $j$ of $i$;

- there is a transition from $x$ to $y$ with $d(x, y) = 1$ and $y_i = x_i - 1$ if and only if $x_i > 0$ and there exists $j$ an inhibitor of $i$ such that $x_j \ge t(j, i)$.

In a nutshell, any inhibition pushes the level of the target vertex towards zero, while, in absence of any inhibition, the level of the vertex is allowed to grow towards its maximum, in a stepwise fashion.

**Definition 4.** An attractor of $\text{AD}(G, m, t)$ is a terminal strongly connected component of the state transition graph. Attractors are called fixed points if they consist of one state, and cyclic attractors otherwise.

This definition is the classic definition of an attractor, modeling the long-term oscillating behavior of a system. The condition of strong connectedness ensures that all states within the attractor are mutually reachable, while terminality ensures that the system's dynamics cannot escape these sets [Comet et al., 2013].

**Remark 1.** The state $x$ with $x_i = 0$ for all $i \in V$ has indegree zero in $\text{AD}(G, m, t)$ for all repressilator graphs $G$ and threshold assignments $t$. In other words, the state where all vertices are at level 0 can only be a source state. This is a consequence of the fact that we only consider repressilators without self-loops: a state where only one vertex is at level 1 cannot see this vertex decrease, because no inhibitions are expressed.

More generally, consider the set $S = \{x \in X \mid x_i < t(i, k) \text{ for all } (i, k) \in E\}$. All states in this set contain only vertices values that are below the thresholds of the interaction graph, meaning that no inhibition is expressed. Thus, any dynamical transition from a state in $S$ can only lead to a state with one increased value (first case in Definition 3). The consequence is that from any state in $S$, there exists a path of successive transitions that exits the set $S$. Moreover, there exists no transition from a state $y \in X \setminus S$ to a state $x \in S$, implying that the states in $S$ cannot be part of an attractor.
For a graph $G$ and a subset $A$ of the vertices, we write $G[A]$ for the subgraph of $G$ induced by $A$.

We call a *subspace* a subset of the state space $X$ obtained by fixing some vertices. In more detail, consider a set $C \subseteq V$ and a map $I: C \to \mathbb{N}$ that satisfies $I(i) \le m_i$ for all $i \in C$. Then the set $\kappa_{C,I} = \{x \in X \mid x_i = I(i) \text{ for all } i \in C\}$ is the subspace of $X$ defined by $C$ and $I$.

It is often useful to view a subspace $\kappa_{C,I}$ as a smaller state space contained in the state space $X$. Given a repressillator $(G, m, t)$, one can consider the subgraph of the asynchronous dynamics AD$(G, m, t)$ induced by the vertices in $\kappa_{C,I}$, and ask whether the dynamics thus obtained can be viewed as the dynamics associated to some repressillator. This is not the case in general, but works when $I(i) = 0$ for all $i \in C$, as described in the following remark.

**Remark 2.** Given a subspace $\kappa_{C,I}$ with $I(i) = 0$ for all $i \in C$, consider the set of vertices $V' = V \setminus C$, and define a maximum level assignment $m'$ as the restriction of $m$ to $V'$. The subspace can be viewed as a state space via the isomorphism $\pi: \kappa_{C,I} \to X'$, with $X' = \prod_{i \in V \setminus C} \{0, \dots, m_i\}$, so that for all $x \in \kappa_{C,I}$, $\pi(x) = (x_i)_{i \in V \setminus C}$. In other words, this isomorphism projects the components of $x$ onto the components in $V \setminus C$. We show that the subgraph of AD$(G, m, t)$ induced by the vertices in $\kappa_{C,I}$ (on the state space $X'$, via the isomorphism $\pi$) is the dynamics AD$(G', m', t')$ associated to the repressillator interaction graph $G' = G[V']$ with threshold assignment $t'$ given by the restriction of $t$ to the edges in $G[V']$ (edges that have both endpoints in $V'$).

- Suppose that there is a transition in AD$(G', m', t')$ from $x$ to $y$ in $\kappa_{C,I}$, and that $y_i = x_i + 1$. Then $i$ is in $V'$, and the transition is also a transition in AD$(G, m, t)$. Hence $x_i < m_i = m'_i$ and $x_j < t(j, i) = t'(j, i)$ for all inhibitors $j$ of $i$, and in particular, for all inhibitors in $V'$. Vice versa, take $x \in \kappa_{C,I}$ and suppose that $x_i < m'_i$ and $x_j < t'(j, i)$ for all inhibitors $j \in V'$ of $i$. Then $x_i < m_i$, and since $x_j = 0$ for all $j$ outside of $V'$, we have $x_j < t(j, i)$ for all inhibitors $j$ of $i$ in $V$. Hence a transition from $x$ to $y$ with $y_i = x_i + 1$ exists in AD$(G, m, t)$ and in its restriction to $\kappa_{C,I}$.

- Suppose that there is a transition in AD$(G', m', t')$ from $x$ to $y$ in $\kappa_{C,I}$, and that $y_i = x_i - 1$. Then $i$ is in $V'$, and the transition is also a transition in AD$(G, m, t)$. Hence $x_i > 0$ and there exists $j \in V$ inhibitor of $i$ such that $x_j \ge t(j, i)$. Since $t(i, j) > 0$, $j$ is not in $C$. Vice versa, take $x \in \kappa_{C,I}$ and suppose that $x_i > 0$ and $x_j \ge t'(j, i)$ for some inhibitor $j \in V'$ of $i$. Then there is a transition from $x$ to $y$ with $y_i = x_i - 1$ in AD$(G, m, t)$, and also in its restriction to $\kappa_{C,I}$.

## 2.1 Stable dominating sets

We now introduce a definition that will be useful for the analysis of repressillator attractors.

**Definition 5.** Let $A \subseteq V$ be a non-empty set of vertices. If there exists no edge $(i, j) \in E$ with $i \in A$ and $j \in A$, then $A$ is called an independent set. If for all
j ∈ V \ A, there exists i ∈ A such that (i, j) ∈ E, then A is called a dominating set. If A is both an independent and dominating set, then it is called a stable dominating set.

The set A of this definition is a set of vertices that do not inhibit each other, and that, taken together, inhibit all vertices outside of A. For $n = 1$, there is only one repressilator interaction graph, the graph with the empty set of edges E, and $A = V = \{0\}$ is its only stable dominating set. Note that the case $A = V$ cannot exist for $n > 1$ since we suppose in this work that the interaction graph is connected, thus preventing V to be a stable dominating set. For $n = 2$, a stable dominating set also always exists:

- If there is an edge from vertex 0 to vertex 1, then $A = \{0\}$ is a stable dominating set, whether an edge from 1 to 0 exists or not.

- If there is an edge from vertex 1 to vertex 0, then $A = \{1\}$ is a stable dominating set, which is not incompatible with the previous case as several stable dominating sets can coexist.

- The case where there is no edge is out of scope since we suppose that the interaction graph is connected. This case could be tackled by considering it as a composition of two models of size $n = 1$.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Left: interaction graph always having a cyclic attractor. Right: interaction graph never having a cyclic attractor. Reproduced from [Sun et al., 2023, Figure 5].</figcaption></figure>

*Example 1.* Consider the graphs in Figure 1. For the graph on the right, $A = \{1, 3\}$ is a stable dominating set (no edges between 1 and 3, while 0 and 2 are inhibited by 1). The graph on the left does not admit any stable dominating set: no single vertex inhibits all other vertices; considering pair of vertices, 0 and 3 are the only vertices that do not inhibit each other, but they do not inhibit vertex 2.

We will use the stable dominating sets of Definition 5 to characterize the fixed points of the dynamics. To this end, given a subset A of V, we define a state $\phi(A) \in X$ associated to A as follows:

$$ \phi(A)_i = \begin{cases} m_i & \text{if } i \in A, \\ 0 & \text{otherwise,} \end{cases} $$
for all $i \in V$, where $\phi(A)_i$ is the $i$-th component of $\phi(A)$. Equivalently, for all $i \in V$, $\phi(A)_i = \mathbf{1}_A(i) \cdot m_i$, where $\mathbf{1}_A$ is the indicator function of $A$.

# 3 Results

## 3.1 Sufficient condition for the existence of cyclic attractors

The following theorem explains the rationale behind the name “stable dominating sets”. The notion of stable dominating set is actually closely related to the notion of kernel as recalled in [Richard and Ruet, 2013], where it is used to prove the same result for a class of Boolean models. Here, the result is generalized to multi-valued networks.

**Theorem 1.** A state $x \in X$ is a fixed point for the dynamics associated to a repressilator interaction graph $G$ if and only if $x = \phi(A)$ for some stable dominating set $A \subseteq V$.

*Proof.* (1) We first show that, if $A \subseteq V$ is a stable dominating set for $G$, then $\phi(A)$ is a fixed point.

For $i$ in $A$, all the inhibitors of $i$ are outside $A$. Hence, at $\phi(A)$, all inhibitors of $i$ are below the threshold required for the inhibition, and $\phi(A)_i$ cannot decrease.

For $i$ outside $A$, there is at least one inhibitor in $A$, at its maximum value, hence above the threshold. Therefore $\phi(A)_i$ cannot increase.

(2) Suppose now that $x$ is a fixed point. Define $A = \{i \in V \mid x_i > 0\}$.

If $i$ is in $A$, since $x$ is a fixed point, all its repressors must be below the relative threshold. Moreover, since the value of $x_i$ cannot increase and all its inhibitors are below threshold, the value of $x_i$ must be maximum. Since all inhibitors $B$ of vertices in $A$ are below the threshold for the inhibition, and all components in $A$ are at maximum levels, all components in $B$ must be at zero, that is, all inhibitors of vertices in $A$ must be outside $A$ (A is an independent set).

If $i$ is outside of $A$, since $x_i$ is zero and cannot increase, it must have an inhibitor that is above threshold, that is, an inhibitor that is in $A$ (A is a dominating set). $\square$

It is noteworthy that the result of Theorem 1 is independent of the chosen threshold assignment.

**Corollary 1.** The dynamics associated to a repressilator interaction graph $G$ has a fixed point if and only if the graph $G$ admits a stable dominating set.

**Corollary 2.** If a repressilator interaction graph $G$ does not admit a stable dominating set, then it has a cyclic attractor.

The previous corollary establishes a sufficient condition for the existence of cyclic attractors, based on the absence of fixed points. Before moving on to consider situations where fixed points and cyclic attractors coexist, we make some simple observations on the dynamics.
**Proposition 1.** If A is a stable dominating set for G with maximum level as-
signment m, then, for any threshold assignment t and for any state x such that
$x_i = 0$ for all $i \in V \setminus A$, there is a path from x to $\phi(A)$ in AD(G, m, t).

*Proof.* Since all the inhibitors of vertices in A are outside A, the components in A are free to increase to their maximum levels. $\square$

**Proposition 2.** If *A* is a stable dominating set for *G* with maximum level as-
signment *m*, then, for any threshold assignment *t* and for any state *x* such that
*x*<sub>*i*</sub> = *m*<sub>*i*</sub> for all *i* ∈ *A*, there is a path from *x* to *φ*(*A*) in AD(*G*, *m*, *t*).

*Proof.* All components outside $\mathcal{A}$ are inhibited by vertices in $\mathcal{A}$ in all states $x$ that satisfy $x_i = m_i$ for all $i \in \mathcal{A}$. $\square$

We say that a vertex *i* oscillates in an attractor *A* if there exists *x*, *y* in *A*
with *x*<sub>*i*</sub> ≠ *y*<sub>*i*</sub>.

**Proposition 3.** If a vertex *i* oscillates in an attractor *A*, then

(i) there exists a state $x \in \mathcal{A}$ such that $x_i = 0$;

(ii) there exists a state $x \in \mathcal{A}$ such that $x_i = m_i$.

*Proof.* If vertex *i* oscillates in an attractor *A*, then there exist a transition be-
tween two states in *A* that decreases the value of component *i*. Say that this
transition is from state *x* to state *y*. This means that at *x* component *i* is inhib-
ited. Since the transition graph is asynchronous, *x* and *y* differ only in component
*i*; therefore, since there are no self-inhibitions, component *i* is inhibited in state
*y* as well, meaning that state *y* has a successor *z* with component *i* satisfying
*z*<sub>*i*</sub> *y*<sub>*i*</sub>, and component *i* can continue to decrease until 0 is reached.

The proof for point (ii) proceeds the same way. $\square$

**3.2 Coexistence of fixed points and cyclic attractors**

We first give a sufficient condition for the coexistence of fixed points and cyclic
attractors, valid in any dimension. In the next section, we show that the condition
is also necessary for $n = 4$.

**Theorem 2.** Consider a repressilator interaction graph *G* and suppose that there exists a stable dominating set *A* such that the subgraph *G*[*V* \ *A*] admits no stable dominating set. Take *B* ≠ ∅ any minimal subset of *V* \ *A* such that *G*[*B*] does not admit a stable dominating set. If all vertices in *B* inhibit all vertices in *V* \ *B*, then there exist a maximum level assignment *m* and a threshold assignment *t* such that the dynamics AD(*G*, *m*, *t*) admits a cyclic attractor.

*Proof.* Let $C = V \setminus B$ and consider a threshold assignment $t: E \to \mathbb{N}^+$ that satisfies the following property: for all $i, k \in B$ and $j \in C$ such that $(i, j) \in E$ and $(i, k) \in E$ are edges in $G$, $t(i, j) \le t(i, k)$. That is, the thresholds for vertices in $B$ to inhibit vertices in $B$ cannot be below the thresholds of inhibitions of vertices in $B$ to vertices in $C$.
Let $\kappa_{C,I}$ be the subspace of $X$ such that $I(i) = 0$ for all $i \in C$, that is, where the vertices in $C$ are fixed to zero. By Remark 2, the restriction $\text{AD}'$ of $\text{AD}(G, m, t)$ to $\kappa_{C,I}$, defined on the state space $X'$ via the isomorphism $\pi: \kappa_{C,I} \to X'$, admits $G[B]$ as interaction graph. Hence, by Corollary 2, the dynamics $\text{AD}'$ admits a cyclic attractor.

Let $\mathcal{A}' \subseteq X'$ be a set of states that defines a cyclic attractor in $\text{AD}'$, and let $\mathcal{A} = \pi^{-1}(\mathcal{A}')$. We want to show that $\mathcal{A}$ is a cyclic attractor in $\text{AD}(G, m, t)$.

Since $\mathcal{A}'$ is strongly connected, $\mathcal{A}$ is also strongly connected. To conclude the proof, we show that $\mathcal{A}$ is terminal, that is, it admits no outgoing transition.

For this, it is sufficient to show that, given a state $x$ in $\mathcal{A}$, for all $j \in C$ there exists $i \in B$ such that $x_i \ge t(i, j)$, meaning that component $j$ is inhibited by $i$ and cannot change. Suppose by contradiction that, for some $j \in C$, $x_i < t(i, j)$ for all $i \in B$ (recall that $j$ is inhibited by all vertices in $B$). Then, by definition of the threshold function $t$, if $(i, k)$ is an edge in $E$ with $k \in B$, we have $x_i < t(i, j) \le t(i, k)$, that is, $x_i$ is below the thresholds for the inhibition from $i$ to any vertex in $B$. Now, recall that state $\pi(x)$ is part of the attractor $\mathcal{A}'$ of $\text{AD}'$. On the other hand, the state $\pi(x)$ satisfies the conditions of Remark 1 $(\pi_i(x) = x_i < t(i, k) = t'(i, k)$ for all $i, k \in B$ with $(i, k)$ an edge in $G[B]$). Therefore $\pi(x)$ cannot be part of an attractor, a contradiction. $\square$

**Remark 3.** The proof of the theorem provides a family of threshold assignments for which $\text{AD}(G, m, t)$ admits both a fixed point and a cyclic attractor, under the stated hypotheses. In particular, we showed that we can always take the constant threshold assignment $t = 1$. The result applies therefore also to Boolean repressilators (systems that satisfy $m_i = 1$ for all $i \in V$).

**Example 2.** Consider the interaction graph $G$ in Figure 2, without taking into account the threshold assignment. This interaction graph contains the stable dominating set $A = \{4\}$, and the interaction graph $G[V \setminus A] = G\{0, 1, 2, 3\}$ contains no stable dominating set. Indeed, any singleton subset of $V \setminus A$ does not inhibit all other vertices in $V \setminus A$, and any subgraph with two or more vertices in $V \setminus A$ contains at least one edge. Consider $B = \{0, 1, 2\} \subset V \setminus A$; it is easy to see that $B$ does not contain a stable dominating set for $G[B]$ for the same reasons as above. Moreover, $B$ is minimal for this property, since any interaction graph in dimension 1 or 2 always contains a stable dominating set, as explained after Definition 5. Finally, since each node in $B$ inhibits all nodes in $V \setminus B = \{3, 4\}$, then Theorem 2 applies: there exists a threshold assignment such that the asynchronous dynamics of $G$ admits a cyclic attractor. An example of such an assignment is the one given in Figure 2, that produces an asynchronous dynamics containing both the fixed point 00004, and the following cyclic attractor:

$$ \{00300, 01300, 02300, 03000, 03100, 03200, 03300, \\ 10300, 11300, 12300, 13000, 13100, 13200, 13300, \\ 20300, 21300, 22300, 23000, 23100, 23200, 23300, \\ 30000, 30100, 30200, 30300, 31000, 31100, 31200, 31300, \\ 32000, 32100, 32200, 32300, 33000, 33100, 33200\} $$
<figure><img src="image_3.png" /><figcaption>Fig. 2. Interaction graph of dimension 5 with a threshold assignment.</figcaption></figure>

### 3.3 Case $n = 3$

We first characterize the only possible cyclic attractor in dimension $n = 3$, which will be used in later proofs.

*Remark 4.* Consider a repressilator G with set of vertices V of size 3, and suppose that, for some maximum level assignment *m* and threshold assignment *t*, AD(*G*, *m*, *t*) admits a cyclic attractor *A* where all three vertices oscillate. Then G consists in an isolated cycle. To see this, first observe that all 3 vertices must have an incoming edge. Then, suppose for a contradiction that one vertex *i* is the source of two edges which target the other two vertices. Then {*i*} is a stable dominating set. By Proposition 3, there exists a state *x* ∈ *A* with *x*<sub>*i*</sub> = *m*<sub>*i*</sub>. Then, by Proposition 2, there is a path in AD(*G*, *m*, *t*) from *x* to *φ}*{*i*}<sub>0</sub>*, which is a fixed point by Theorem 1, a contradiction.

The remark implies, in particular, that in a cyclic attractor in dimension 3, for each pair of vertices *i* and *j* that oscillate in the attractor, there exists *x* ∈ *A* such that *x*<sub>*i*</sub> = 0 and *x*<sub>*j*</sub> = 0.

Note that this property does not hold in general for attractors in higher dimensions. Consider for instance the repressilator interaction graph with 6 vertices defined in Figure 3. The asynchronous dynamics associated to this graph has one cyclic attractor with states:

$$ \begin{aligned} \{010200, 011200, 012000, 012100, 012200, \\ 100002, 100012, 100020, 100021, 100022, \\ 110000, 110001, 110002, 110010, 110011, 110012, 110020, \\ 110021, 110100, 110200, 111000, 111100, 111200, 112000, 112100\} \end{aligned} $$

Taking *i* = 0 and *j* = 1, we observe that both vertices oscillate in the attractor, but the attractor does not contain a state *x* with *x*<sub>*i*</sub> = *x*<sub>*j*</sub> = 0.
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Interaction graph of dimension 6 with a threshold assignment.</figcaption></figure>

### 3.4 Case $n = 4$

In dimension $n = 4$, we can fully characterize the repressilator interaction graphs that admit a dynamics with a cyclic attractor. We start by showing that, in dimension 4, if the dynamics has a cyclic attractor, then the interaction graph cannot have a stable dominating set that contains more than one vertex. Intuitively, a stable dominating set cannot intersect the negative cycle associated to the cyclic attractor.

**Lemma 1.** Consider $n = 4$. Suppose that $\text{AD}(G, m, t)$ has a cyclic attractor. Then $G$ cannot have a stable dominating set of cardinality two or larger.

*Proof.* Observe first that, by [Richard, 2010, Theorem 1], $G$ must admit a negative cycle, therefore a cycle $C$ of length 3.

Since all pairs of vertices in $C$ are connected by at least one edge, any stable dominating set $A$ intersects $C$ in at most one vertex. Suppose that $A$ contains two vertices, and therefore a vertex $i$ in $C$ and a vertex $j$ outside $C$. Write $A = \{i, j\}$ and $C = \{i, k, h\}$.

Suppose that the vertices in $C$ are the only vertices that oscillate in the attractor. Then $j$ is fixed in the attractor. If $j$ is not the target of any vertex, then the value of component $j$ is fixed to $m_j$ in all attractors. Since we assumed that the directed graph underlying $G$ is connected, $j$ must be an inhibitor of at least one vertex in $\{k, h\}$, meaning that the value of its target is fixed to zero in any attractor, which precludes the existence of a cyclic attractor.

Therefore $j$ is the target of either $k$ or $h$. Assume without loss of generality that $j$ is the target of $k$. By Proposition 3 (ii), the attractor contains a state $x$ with $x_k = m_k$, that is, where component $k$ is at maximum level and, therefore, above the threshold for inhibition of $j$. Since $j$ is fixed in the attractor, its fixed value must be 0. That is, the attractor is contained in the 3-dimensional subspace $S = \{x \in X \mid x_j = 0\}$. By Remark 2, the restriction of the dynamics to $S$ is exactly a repressilator dynamics associated to the interaction graph $G[C]$. Since it admits a cyclic attractor, by Remark 4 $G[C]$ consists of an isolated cycle. Moreover, there exists a state $x$ in the attractor where $x_i = m_i$ and $x_k = x_h = 0$. This means that $j$ is not inhibited in $x$, a contradiction. Therefore all four vertices must oscillate in the attractor.

By definition of a stable dominating set, $k$ and $h$ are inhibited by either $i$ or $j$. On the other hand, neither $i$ or $j$ can be an inhibitor of both $k$ and $h$. Indeed, suppose that $i$ inhibits both $k$ and $h$ (the same proof works if we take $j$ as the
inhibitor). By Proposition 3 (ii), we can take a state $x$ in the attractor where $x_i = m_i$ and both components $k$ and $h$ are inhibited. By the definition of the dynamics, the attractor contains therefore a state $y$ where $y_k = y_h = 0$. On the other hand, since $i$ does not inhibit $j$, the value of component $j$ can increase to $m_j$. That is, the attractor contains a state $z$ that satisfies $z_i = m_i$, $z_j = m_j$. By Proposition 2, there is a path from $z$ to the fixed point $\phi(A)$, a contradiction.

We can therefore assume that $i$ inhibits $k$ and $j$ inhibits $h$. Since $i, k, h$ form a cycle and $h$ is not inhibited by $i, h$ inhibits $i$.

Suppose that there is no edge $(k, i) \in E$. Using Proposition 3, take a state $x$ in the attractor where $x_j = m_j$. Since $j$ inhibits $h$, there also exists a state $y$ in the attractor where $y_j = m_j$ and $y_h = 0$. Since $i$ is only inhibited by $h$, then there exists a state $z$ in the attractor where $z_j = m_j$, $z_h = 0$ and $z_i = m_i$. By Proposition 2, there is a path from $z$ to the fixed point $\phi(A)$, which is a contradiction.

Suppose now that there is an edge $(k, i) \in E$. If there also exists an edge $(k, j) \in E$, then $A' = \{k\}$ is also a stable dominating set; using Proposition 3, there exists a state $x \in X$ so that $x_k = m_k$ and by Proposition 2, there is a path from $x$ to $\phi(A')$, a contradiction. Finally, if there is an edge $(k, i) \in E$ but $(k, j) \notin E$, then this means that $A'' = \{k, j\}$ is also a stable dominating set, and that vertex $k \in A''$ inhibits vertices $i, h \in V \setminus A''$; as shown above, this also leads to a contradiction. $\square$

**Theorem 3.** For $n = 4$, if AD(G, $m, t$) admits both a fixed point and a cyclic attractor for some maximum level assignment $m$ and threshold assignment $t$, then $G$ satisfies the conditions of Theorem 2. More precisely:

1. AD(G, $m, t$) admits exactly one fixed point, with a stable dominating set $A$ of size one;

2. G[$B$] with $B = V \setminus A$ has no stable dominating set, and $B$ is minimal for this property;

3. all vertices in $B$ inhibit the vertex in $A$.

In addition, AD(G, $m, t$) has exactly one cyclic attractor.

*Proof.* Consider the minimum subspace $\kappa_{C,I}$ of $X$ that contains the cyclic attractor, meaning that all variables in $V \setminus C$ oscillate in the attractor. The interaction graph of the restriction of the dynamics to $\kappa_{C,I}$ is a subgraph of G[$V \setminus C$]. By [Richard, 2010, Theorem 1], G[$V \setminus C$] must admit a negative cycle. Since loops are excluded and all arcs are negative, G[$V \setminus C$], and therefore $G$, must contain a cycle of length 3. In particular, $C$ has cardinality at most one, and at least three vertices oscillate in the cyclic attractor.

(1) By Theorem 1, $G$ has a stable dominating set $A$. By Lemma 1, $A$ has size one. Say $A = \{i\}$. By Proposition 2 and Proposition 3, $i$ does not oscillate in the cyclic attractor. Therefore this attractor oscillates in exactly three dimensions, and there is only one stable dominating set, and therefore only one fixed point (by Theorem 1).
(2) We know that $i$ is fixed in the cyclic attractor, and, by Proposition 2, cannot be fixed at maximum level. Therefore, it must be inhibited in all states in the attractor. Since it is inhibited and fixed in the attractor, it must take value zero in all states in the attractor. That is, the attractor is contained in $S = \{x \in X \mid x_i = 0\}$.

Therefore the vertices in $B$ form a cycle. By Remark 2, the restriction of the dynamics to $S$ is a repressilator dynamics associated to the interaction graph $G[B]$, and by Remark 4, $G[B]$ is an isolated cycle, and has no stable dominating set while all proper subsets of $B$ admit a stable dominating set.

(3) Suppose that a vertex $j \in B$ does not inhibit $i$. By Remark 4 there exists a state $x$ in the attractor where the components corresponding to $B \setminus \{j\}$ are zero, and $i$ is not inhibited and is free to increase, a contradiction.

Finally, again by Remark 4, the cyclic attractor is unique (all cyclic attractors contain the state where the vertex in $A$ is zero, two vertices in $B$ are zero and the remaining vertex is at maximum level). $\square$

# 4 Conclusion

Repressilators are biological networks composed only of inhibitions between components, used in synthetic biology for their ability to exhibit oscillatory behavior. However, in dimensions higher than 3, not all repressilators oscillate: in some cases, the attractors are all fixed points. In this paper, we propose a method to determine if a given repressilator of dimension $n$ might present a cyclic attractor. This method is solely based on the interaction graph without threshold assignment, meaning that we avoid both the combinatorial explosion due to the computation of the state transition graph, and the enumeration of the possible threshold assignments.

A possible extension of this work could explore the applicability of a result analogous to Theorem 2 with a weaker premise, making it less specific and more widely applicable. Networks that are not repressilators and that might contain positive interactions could also be considered. A complete characterization of the asymptotic dynamics of repressilators in dimension 5 or higher also remains to be investigated. Linking the theory and results developed in this work to and-nets (such as in [Richard and Ruet, 2013]) could prove beneficial to this aim.

**Acknowledgments.** ET was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). HS was funded by the China Scholarship Council.

# References

* Akutsu et al., 2012. Akutsu, T., Kosub, S., Melkman, A. A., and Tamura, T. (2012). Finding a Periodic Attractor of a Boolean Network. *IEEE/ACM Transactions on Computational Biology and Bioinformatics*, 9(5):1410–1421.
Batt et al., 2008. Batt, G., de Jong, H., Page, M., and Geiselmann, J. (2008). Symbolic reachability analysis of genetic regulatory networks using discrete abstractions. *Automatica*, 44(4):982–989.

Bernot et al., 2004. Bernot, G., Comet, J.-P., Richard, A., and Guespin, J. (2004). Application of formal methods to biological regulatory networks: extending Thomas’ asynchronous logical approach with temporal logic. *Journal of Theoretical Biology*, 229(3):339–347.

Comet et al., 2013. Comet, J.-P., Noual, M., Richard, A., Aracena, J., Calzone, L., Demongeot, J., Kaufman, M., Naldi, A., Snoussi, E. H., and Thieffry, D. (2013). On Circuit Functionality in Boolean Networks. *Bulletin of Mathematical Biology*, 75(6):906–919.

de Jong, 2002. de Jong, H. (2002). Modeling and simulation of genetic regulatory systems: A literature review. *Journal of Computational Biology*, 9(1):67–103.

Elowitz and Leibler, 2000. Elowitz, M. B. and Leibler, S. (2000). A synthetic oscillatory network of transcriptional regulators. *Nature*, 403(6767):335–338.

Gadouleau, 2020. Gadouleau, M. (2020). On the influence of the interaction graph on a finite dynamical system. *Natural Computing*, 19(1):15–28.

Goh et al., 2008. Goh, K.-I., Kahng, B., and Cho, K.-H. (2008). Sustained oscillations in extended genetic oscillatory systems. *Biophysical Journal*, 94(11):4270–4276.

Kauffman, 1969. Kauffman, S. A. (1969). Metabolic stability and epigenesis in randomly constructed genetic nets. *Journal of Theoretical Biology*, 22(3):437–467.

Melkman et al., 2010. Melkman, A. A., Tamura, T., and Akutsu, T. (2010). Determining a singleton attractor of an AND/OR Boolean network in $O(1.587^n)$ time. *Information Processing Letters*, 110(14-15):565–569.

Mendes et al., 2018. Mendes, N. D., Henriques, R., Remy, E., Carneiro, J., Monteiro, P. T., and Chaouiya, C. (2018). Estimating attractor reachability in asynchronous logical models. *Frontiers in Physiology*, 9.

Naldi et al., 2011. Naldi, A., Remy, E., Thieffry, D., and Chaouiya, C. (2011). Dynamically consistent reduction of logical regulatory graphs. *Theoretical Computer Science*, 412(21):2207–2218. Selected Papers from the 7th International Conference on Computational Methods in Systems Biology.

Page, 2019. Page, K. M. (2019). Oscillations in well-mixed, deterministic feedback systems: Beyond ring oscillators. *Journal of Theoretical Biology*, 481:44–53.

Paulevé et al., 2012. Paulevé, L., Magnin, M., and Roux, O. (2012). Static analysis of Biological Regulatory Networks dynamics using abstract interpretation. *Mathematical Structures in Computer Science*, pages 1–35.

Paulevé and Richard, 2012. Paulevé, L. and Richard, A. (2012). Static analysis of boolean networks based on interaction graphs: A survey. *Electronic Notes in Theoretical Computer Science*, 284:93–104. Proceedings of the 2nd International Workshop on Static Analysis and Systems Biology (SASB 2011).

Perez-Carrasco et al., 2018. Perez-Carrasco, R., Barnes, C. P., Schaerli, Y., Isalan, M., Briscoe, J., and Page, K. M. (2018). Combining a toggle switch and a repressilator within the ac-dc circuit generates distinct dynamical behaviors. *Cell systems*, 6(4):521–530.

Potvin-Trottier et al., 2016. Potvin-Trottier, L., Lord, N. D., Vinnicombe, G., and Paulsson, J. (2016). Synchronous long-term oscillations in a synthetic gene circuit. *Nature*, 538(7626):514–517.

Richard, 2010. Richard, A. (2010). Negative circuits and sustained oscillations in asynchronous automata networks. *Advances in Applied Mathematics*, 44(4):378–392.
Richard and Ruet, 2013. Richard, A. and Ruet, P. (2013). From kernels in directed graphs to fixed points and negative cycles in boolean networks. *Discrete Applied Mathematics*, 161(7):1106–1117.

Sun et al., 2023. Sun, H., Folschette, M., and Magnin, M. (2023). Condition for periodic attractor in 4-dimensional repressilators. In Pang, J. and Niehren, J., editors, *21st International Conference on Computational Methods in Systems Biology (CMSB 2023)*, pages 184–201, Cham. Springer Nature Switzerland.

Thomas, 1973. Thomas, R. (1973). Boolean formalization of genetic control circuits. *Journal of theoretical biology*, 42(3):563–585.

Thomas, 1991. Thomas, R. (1991). Regulatory networks seen as asynchronous automata: a logical description. *Journal of theoretical biology*, 153(1):1–23.