Articulo
NUMBER OF FIXED POINTS AND DISJOINT CYCLES IN MONOTONE BOOLEAN NETWORKS
SIAM JOURNAL ON DISCRETE MATHEMATICS
Registro en:
1151265
1151265
Autor
Aracena-Lucero, Julio Bernardo
Richard, Adrien
Salinas-Ayala, Lilian
Institución
Resumen
Given a digraph G, much attention has focused on the maximum number phi(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 phi(G) <= 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 monotone Boolean network with interaction graph G. We establish new upper and lower bounds on phi(m) (G) that depend on the cycle structure of G. In addition to tau, the involved parameters are the maximum number v of vertex-disjoint cycles, and the maximum number V* of vertex-disjoint cycles verifying some additional technical conditions. We improve the feedback bound 2(tau) by proving that phi(m)(G) is at most the largest sublattice of {0, 1}" without chain of size v vertical bar 2, and without another forbidden pattern described by two disjoint antichains of size v' + 1. Then, we prove two optimal lower bounds: phi(m) (G) > v+ 1 and phi(m) (G) >2(v*) As a consequence, we get the following characterization: phi(m)(G) = 2(tau) if and only if v* = tau. s another consequence, we get that if c is the maximum length of a chordless cycle of G, then 2(v/3c) < phi(m) (G) < 2cv. 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. Regular 2015 FONDECYT FONDECYT