2024/10/07 by Aracena, Julio, Astete-Elguin, Raúl
#Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics
paper · doi:10.48550/arxiv.2410.05200
This paper proposes a new parameter for studying Boolean networks: the independence number. We establish that a Boolean network is k-independent if, for any set of k variables and any combination of binary values assigned to them, there exists at least one fixed point in the network that takes those values at the given set of k indices. In this context, we define the independence number of a network as the maximum value of k such that the network is k-independent. This definition is closely related to widely studied combinatorial designs, such as "k-strength covering arrays", also known as Boolean sets with all k-projections surjective. Our motivation arises from understanding the relationship between a network's interaction graph and its fixed points, which deepens the classical paradigm of research in this direction by incorporating a particular structure on the set of fixed points, beyond merely observing their quantity. Specifically, among the results of this paper, we highlight a condition on the in-degree of the interaction graph for a network to be k-independent, we show that all regulatory networks are at most n/2-independent, and we construct k-independent networks for all possible k in the case of monotone networks with a complete interaction graph.