A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks
Adrien Richard
Abstract
We are interested in fixed points in Boolean networks, i.e. functions f from {0,1}^n to itself. We define the subnetworks of f as the restrictions of f to the hypercubes contained in {0,1}^n, and we exhibit a class F of Boolean networks, called even or odd self-dual networks, satisfying the following property: if a network f has no subnetwork in F, then it has a unique fixed point. We then discuss this ``forbidden subnetworks theorem''. We show that it generalizes the following fixed point theorem of Shih and Dong: if, for every x in {0,1}^n, there is no directed cycle in the directed graph whose the adjacency matrix is the discrete Jacobian matrix of f evaluated at point x, then f has a unique fixed point. We also show that F contains the class F' of networks whose the interaction graph is a directed cycle, but that the absence of subnetwork in F' does not imply the existence and the uniqueness of a fixed point.
Full Text: PostScript PDF