Thesis Summary:

In this thesis, we define a new parameter for studying Boolean networks, called 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 cov- ering 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 cardinality. Specifically, we focus on studying interaction graphs that admit k-independent networks and show that the complete graph without loops with linear-type activation functions achieves maximum nontrivial strength. Furthermore, we present constructions that demonstrate the existence of k- independent networks on n variables with disconnected, connected and strongly connected interac- tion graphs. We also study necessary conditions for a network to be k-independent. Finally, we observe that computational simulations failed to find examples of monotone k-independent networks. This observation motivates Section 4.1 of this thesis, where we use another classical combinatorial design, called a Steiner system, to construct monotone k-independent networks with complete loopless interaction graphs.