Preprint 2016-04
Julio Aracena, Adrien Richard, Lilian Salinas:
Number of fixed points and disjoint cycles in monotone Boolean networks
Abstract:
Given a digraph G, a lot of attention has been has been paid to the maximum number ϕ(G) of fixed points in a Boolean network f:{0,1}n→{0,1}n with G as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the classical upper bound ϕ(G)≤2τ, where τ is the minimum size of a feedback vertex set of G. In this paper, we study the maximum number ϕm(G) of fixed points in a monotone Boolean network with interaction graph G. We establish new upper and lower bounds on ϕm(G) that depend on the cycle structure of G. In addition to τ, the involved parameters are the maximum number ν of vertex-disjoint cycles, and the maximum number ν∗ of vertex-disjoint cycles verifying some additional technical conditions. We improve the classical upper bound 2τ by proving that ϕm(G) is at most the largest sub-lattice of {0,1}τ without chain of size ν+1, and without another forbidden-pattern of size 2ν∗. Then, we prove two optimal lower bounds: ϕm(G)≥ν+1 and ϕm(G)≥2ν∗. As a consequence, we get the following characterization: ϕm(G)=2τ if and only if ν∗=τ. As another consequence, we get that if c is the maximum length of a chordless cycle of G then 2ν/3c≤ϕm(G)≤2cν. Finally, with the technics introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph.
