Towards a solution of the transient problem for Boolean monomial dynamics

Abstract

A problem of interest in finite dynamical systems is to determine when such a system reaches equilibrium, i.e., under what conditions is it a fixed point system. Moreover, given a fixed point system, how many time steps are required to reach a fixed point, i.e., what is its transient? Bollman and Colón have shown that a Boolean Monomial Dynamical System (BMDS) f is a fixed point system if and only if every strongly connected component of the dependency graph Gf of f is primitive and in fact, when Gf is strongly connected, the transient of f is equal to the exponent of Gf . Furthermore, every directed graph gives rise to a unique BMDS and hence every example of a primitive graph with known exponent gives us an example of a fixed point BMDS with known transient. Unfortunately, the general problem of determining the exponent of a primitive graph is unsolved. In this work we give several families of primitive graphs for which we can determine the exponent and hence the transient of the corresponding BMDS.

Un problema de interés en sistemas dinámicos finitos es determinar cuándo tales sistemas alcanzan equilibrio; es decir, bajo cuales condiciones es un sistema de punto fijo. Por otra parte, dado un sistema de punto fijo, cuánta cantidad de pasos son requeridos para alcanzar el punto fijo; es decir, icuál es su tiempo de transición?. Bollman y Colón han mostrado que un Sistema Dinámico Monomial Booleano (SDMB) f es un sistema de punto fijo sí y solo sí cada componente fuertemente conecto del grafo de dependencia Gf de f es primitivo y en efecto, cuando Gf es fuertemente conecto, el tiempo de transición de f es igual a el exponente de Gf Además, cada grafo dirigido da lugar a un único SDMB y por tanto todo ejemplo de un grafo primitivo con exponente conocido provee un ejemplo de un SDMB de punto fijo con tiempo de transición conocido. Desafortunadamente, el problema general de determinar el exponente de un grafo primitivo es abierto. En este trabajo se muestran varias familias de grafos primitivos para las cuales se puede determinar el exponente y por tanto el tiempo de transición de los correspondientes SDMB.