Pre-Publicación 2024-24
Julio Aracena, Raúl Astete-Elguin:
K-independent boolean networks
Abstract:
This paper proposes a new parameter for studying Boolean networks: the indepen-3 dence number. We establish that a Boolean network is k-independent if, for any set of k variables4 and any combination of binary values assigned to them, there exists at least one fixed point in the5 network that takes those values at the given set of k indices. In this context, we define the indepen-6 dence number of a network as the maximum value of k such that the network is k-independent. This7 definition is closely related to widely studied combinatorial designs, such as “k-strength covering8 arrays”, also known as Boolean sets with all k-projections surjective. Our motivation arises from9 understanding the relationship between a network’s interaction graph and its fixed points, which10 deepens the classical paradigm of research in this direction by incorporating a particular structure11 on the set of fixed points, beyond merely observing their quantity. Specifically, among the results12 of this paper, we highlight a condition on the in-degree of the interaction graph for a network to13 be k-independent, we show that all regulatory networks are at most n/2-independent, and we con-14 struct k-independent networks for all possible k in the case of monotone networks with a complete15 interaction graph.
