Given a digraph $G$, a lot of attention has been deserved on the maximum number $\phi(G)$ of fixed points in a Boolean network $f:\{ 0,1\}^n\to\{ 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 $\phi(G)\leq 2^{ \tau}$, where $\tau$ is the minimum size of a feedback vertex set of $G$. In this paper, we study the maximum number $\phi_m(G)$ of fixed points in a { \em monotone} Boolean network with interaction graph $G$. We establish new upper and lower bounds on $\phi_m(G)$ that depends on the cycle structure of $G$. In addition to $\tau$, the involved parameters are the maximum number $\nu$ of vertex-disjoint cycles, and the maximum number $\nu^{ *}$ of vertex-disjoint cycles verifying some additional technical conditions. We improve the classical upper bound $2^\tau$ by proving that $\phi_m(G)$ is at most the largest sub-lattice of $\{ 0,1\}^\tau$ without chain of size $\nu+1$, and without another forbidden-pattern of size $2\nu^{ *}$. Then, we prove two optimal lower bounds: $\phi_m(G)\geq \nu+1$ and $\phi_m(G)\geq 2^{ \nu^{ *}}$. As a consequence, we get the following characterization: $\phi_m(G)=2^\tau$ if and only if $\nu^{ *}=\tau$. As another consequence, we get that if $c$ is the maximum length of a chordless cycle of $G$ then $2^{ \nu/3^c}\leq\phi_m(G)\leq 2^{ c\nu}$. 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.
Categories: math.CO cs.DM cs.IT math.IT q-bio.MN
