\({k}\)-Independent Boolean Networks

Abstract. This paper proposes a new parameter for studying Boolean networks: the independence number. We establish that a Boolean network is [Formula: see text]-independent if, for any set of [Formula: see text] 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 [Formula: see text] indices. In this context, we define the independence number of a network as the maximum value of [Formula: see text] such that the network is [Formula: see text]-independent. This definition is closely related to widely studied combinatorial designs, such as “[Formula: see text]-strength covering arrays,” also known as Boolean sets with all [Formula: see text]-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 [Formula: see text]-independent, we show that all unate networks are at most [Formula: see text]-independent, and we construct [Formula: see text]-independent networks for all possible [Formula: see text] in the case of monotone networks with a complete interaction graph.