Estudio de Modelos Discretos: Estructura y Dinámica

Abstract

En esta tesis hemos estudiado dos problemas: el primero consiste en encontrar condiciones mínimas para obtener una cierta clase de recubrimientos del plano discreto mediante cuadrados y el segundo corresponde al estudio de redes Booleanas.

El problema de recubrimiento por cuadrados nace como una variante del problema de embaldosado. El problema de embaldosado consiste en cubrir el plano discreto, o una parte de éste, sin dejar hoyos y sin superponer baldosas con un número finito de formas distintas. El caso estudiado consiste en cubrir completamente el plano discreto usando sólo cuadrados que pueden superponerse, pero no pueden compartir bordes ni vértices (recubrimiento fuerte). Además, se estudia el caso donde se permite dejar zonas de tamaño acotado sin cubrir y donde todos los cuadrados en el recubrimiento deben estar conectados (recubrimiento débil). Hemos probado que, en el caso donde todos los cuadrados tienen el mismo tamaño e intersectan el mismo número de cuadrados, los recubrimientos fuertes y débiles presentan cotas inferiores para el tamaño y número de cuadrados que los intersectan. Además, para un tamaño de cuadrado dado, mostramos una cota superior de orden lineal para el número de cuadrados que lo intersectan en un recubrimiento sea fuerte o débil,

El segundo problema trata de redes Booleanas, las que fueron introducidas por S. Kauffman (1969) con el objeto de modelar las redes de regulación génica. El primer aspecto estudiado son las redes Booleanas cuyo grafo asociado es por capas. Probamos que el comportamiento límite de este tipo de redes queda completamente determinado por el estado inicial de los nodos en la primera capa, y que los atractores de estas redes son de largo potencia de dos. Más aún, en el caso que todas las bucles sean monótonas crecientes todos los atractores son puntos fijos. El segundo aspecto estudiado es la robustez de la dinámica y del comportamiento límite de una red Booleana frente a distintos esquemas de actualización (paralelo, secuencial por bloques o secuencial). Cada esquema de actualización permite definir un grafo con signo, los resultados obtenidos prueban que si dos esquemas de actualización generan el mismo grafo con signo, estas redes tienen exactamente el mismo comportamiento dinámico. Por otro lado, dado que los puntos fijos son invariantes frente a los distintos esquemas de actualización, nos concentramos en estudiar cómo pequeños cambios en el esquema de actualización producen diferencias en el conjunto de ciclos dinámicos asociados a una red Booleana. Uno de los principales resultados es el que muestra que, dado un esquema de actualización es posible encontrar otro con el cual no comparte ciclos dinámicos. Por último, presentamos un algoritmo que opera como un filtro de ciclos dinámicos para redes Booleanas donde todos los circuitos son positivos. Dada una red Booleana, que tiene sólo circuitos positivos, este filtro permite encontrar en tiempo polinomial una nueva red Booleana que tiene exactamente los mismos puntos fijos, pero no tiene ningún ciclo dinámico. Este algoritmo permite, además, encontrar un punto fijo de la red Booleana en tiempo polinomial.