La intrincada dinámica del operador de clanes

La clase de todas las gráficas \(\mathcal{G}\) junto con un operador \(\Phi:\mathcal{G}\rightarrow \mathcal{G}\) constituyen un sistema dinámico de gráficas. Se presta especial atención al efecto de aplicar los respectivos operadores iterados: \(\Phi^0(G)=G\), \(\Phi^{n+1}(G)=\Phi(\Phi^n(G))\). Muchas preguntas naturales surgen en este contexto, incluyendo cuáles gráficas son \(\Phi\)-invariantes (\(\Phi(G)\cong G\)),  \(\Phi\)-convergentes (\(\Phi^n(G)\cong \Phi^m(G)\) para algunos \(n<m\)) o  \(\Phi\)-divergentes (\(\lim_{n\rightarrow\infty} |\Phi^n(G)|=\infty\)).

En particular, el operador de clanes \(K\) transforma una gráfica \(G\) en su gráfica de clanes \(K(G)\), que es la gráfica de intersección de los clanes (maximales) de \(G\). El operador de clanes es uno de los más estudiados debido a la enorme riqueza del correspondiente sistema dinámico de gráficas. Las gráficas de clanes han sido usadas en Gravitación Cuántica de Lazos para explicar cómo la espuma de espacio-tiempo cuántico podría emerger de una realidad discreta más básica que podría conformar al universo a la escala de la longitud de Planck.

Más recientemente, el problema de la decidibilidad de la \(K\)-divergencia se ha empezado a estudiar. Para ello, algunos circuitos y compuertas lógicas han sido simulados dentro de la dinámica del operador de clanes. Resultados preliminares parecen indicar que la dinámica del operador de clanes tiene al menos el poder de cómputo de un Autómata Linealmente Acotado (como las computadoras con memoria finita, pero no como las máquinas de Turing).

En ésta plática, vamos a mostrar una panorámica muy visual de los principales avances sobre el tema en los últimos 50 años.

Esta plática está basada en diversos trabajos de C. Cedillo, F. Escalante, F. Larrión, V. Neumann-Lara, M. Pizaña, J. Szwarcfiter, R. Villarroel-Flores entre otros.