Abstract

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 being 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 unate 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.