Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks

International audienceGiven a digraph G, a lot of attention has been deserven on 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 feedback 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 depends 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 feedback bound 2 τ by proving that φ m (G) is at most the largest sub-lattice of {0, 1} τ without chain of size ν + 2, and without another forbidden pattern described by two disjoint antichains of size ν * + 1. 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 ν/3 c ≤ φ m (G) ≤ 2 cν. Finally, with the techniques introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph