Pila de arena

Fig.1. Ejemplo intuitivo de pila de arena.

El modelo de pilas de arena es un modelo matemático diseñado para analizar y explicar el comportamiento de la autoorganización crítica a través de la teoría de grafos y la teoría de autómatas celulares utilizando herramientas algebraicas. Considere una pila de arena o un reloj de arena apenas girado, si la pendiente es muy alta, la pila está lejos de encontrarse en equilibrio y colapsará hasta que la pendiente promedio llegue a un valor crítico en el cual el sistema es apenas estable bajo perturbaciones pequeñas.

Desde el planteamiento del modelo por Bak, Tang y Wiesenfeld como ejemplo de autoordenamiento crítico en un sistema dinámico el modelo ha sido estudiado en rejillas (grids) en $\mathbb {Z} ^{d}$, en grafos no k-regulares y hasta en grafos arbitrarios.

Modelo BTW

Fig. 2. ASM en una rejilla (red cuadrada).

Fig. 3. ASM en una malla de caras hexagonales (rejilla hexagonal).

Fig. 4. ASM en una malla de caras triangulares (rejilla triangular).

El modelo de las pilas de arena está definido por una función z y una regla σ donde:

${\begin{matrix}z:\mathbb {Z} \times \mathbb {Z} \longrightarrow \mathbb {N} \cup {\varnothing }\\(x,y)\longmapsto f(x,y)\end{matrix}}$

y si $z(x,y)>K$

$\sigma =\left\{{\begin{matrix}(x,y)\rightarrow z(x,y)-4\\z(x\pm 1,y)\rightarrow z(x\pm 1,y)+1\\(x,y\pm 1)\rightarrow z(x,y\pm 1)+1\end{matrix}}\right.$

El modelo se establece con condiciones iniciales arbitrarias de forma que $z(x,y)>>K$ en al menos un punto; donde K es un número natural que se llamará valor crítico. Si z(x,y) supera K se dirá que el punto (x,y) en inestable y el sistema evoluciona por medio de $\sigma$ hasta parar y estabilizarse. Si el grafo es conexo e infinito y el número de puntos inestables es finito se puede garantizar que tras un número finito de aplicaciones de la regla $\sigma$ el sistema no tendrá puntos inestables.

Intuitivamente z(x,y) corresponde al valor absoluto de la pendiente de la pila de arena en el punto (x,y). Si en un punto (x,y) la pendiente es muy empinada entonces los granos de arena se desploman hacia los puntos vecinos reduciendo la pendiente en (x,y), pero aumentando la pendiente en los puntos vecinos. Ahora, si después de esto la pendiente es muy grande en los vecinos de (x,y), los granos se desplomarán hacia los vecinos de los vecinos de (x,y) y así sucesivamente, creando una avalancha hasta que el sistema se estabilice. De esta forma se puede ver que una mínima perturbación local es capaz de crear una avalancha de gran tamaño y hacer que el sistema se autoorganice hasta llegar a una configuración estable.

Dos configuraciones iniciales $\sigma$ y $\sigma$’ son equivalentes si y solo si al estabilizarse resultan en la misma configuración. El estado crítico de z es único y no depende del número de desplomes ni el orden de dichos desplomes en el proceso de estabilización. Su evolución está caracterizado por correlaciones que siguen una ley de potencias (power law) en espacio y tiempo.

Historia

En 1987, Bak, Tang y Wiesenfeld (BTW) introdujeron un modelo para ilustrar lo que llamaron autoorganización crítica y dar una explicación al fenómeno del ruido 1/f, un fenómeno recurrente en física. En particular en el área de Sistemas Dinámicos y Caos, con aplicación como el estudio del fenómeno de turbulencia, modelos de incendios forestales, etc. Mostrando que sistemas con dinámicas simples pueden llevar al surgimiento de estructuras complejas que resultan en estados estacionarios con propiedades particulares en sus puntos críticos.

Algunos años más tarde Deepak Dhar generalizó el modelo, caracterizando la estructura de grupo abeliano obtenida sobre las configuraciones de pilas de arena al definir sobre aquellas una operación aditiva. Dhar llamó este modelo generalizado el Modelo Abeliano de Pilas de Arena (ASM por sus siglas en inglés:Abelian Sandpile Model ). Mostró también una correspondencia 1-1 entre las configuraciones recurrentes del ASM y los rooted spanning trees del grafo por medio del llamado Algoritmo de Quemado (Burning Algorithm). Esta correspondencia le permitió a Priezzhev computar las probabilidades de altura en dimensión 2 en el límite de volumen infinito.

Dhar y Majumdar estudiaron el modelo en el Bethe lattice (árbol binario sin raíz) obteniendo importantes resultados en cuanto a tamaños y distribuciones de avalanchas. Desde el planteamiento del grupo abeliano de Pilas de Arena del conjunto de configuraciones recurrentes se ha reintroducido el modelo en la literatura matemática bajo el nombre de “juego de disparo de partículas”.

Desde la primera formulación del modelo se han planteado numerosas variaciones al planteamiento original del ASM cambiando reglas, dependencias, dimensiones, etcétera; resultando en un estudio de comportamientos de autoordenamiento crítico y de la naturaleza fuertemente no-local del modelo (agregar un grano en un punto particular puede influenciar la altura de puntos muy lejanos).

El modelo de Zhang, por ejemplo, es una variación no trivial del modelo BTW en el cual las alturas no son discretas con valores en N, sino que son cantidades continuas no negativas (R+). El concepto de autoordenamiento crítico se ha convertido en algo muy popular y es utilizado en diversas áreas incluyendo las Ciencias Naturales como la geología y la biología.

Definición del modelo Abeliano de pilas de arena

A diferencia del modelo BTW, el modelo abeliano de pilas de arena (ASM), planteado por D. Dhar, generaliza el planteamiento inicial a grafos arbitrarios conexos donde el desplome no depende de las pendientes sino de la altura de la pila en cada punto. El punto crítico K del modelo original es sustituido por d(v), el grado del vértice v.

Si el número de granos es igual o mayor al grado del vértice, dicho vértice se dice inestable. Todo vértice inestable se estabilizará donándole un grano a cada uno de sus vértices vecinos. Este proceso lleva el nombre de desplome. Una serie de desplomes resultantes en una configuración estable se conoce como avalancha.

Definición formal en grafos finitos

Considérese un grafo finito conexo de $N$ vértices. Para cada vértice $i$ se asigna un entero variable $z_{i}$ y se definen dos reglas:

1. Adicionar un grano de arena: se escoge un vértice $i$ aleatoriamente y se incrementa $z_{i}$ por $1$. Los demás $z_{j},j\neq i$ permanecen igual.
2. Regla de desplome: se define una matriz $\Delta \in M_{\mathbb {N} \times \mathbb {N} }(\mathbb {Z} )$ y $N$ valores críticos $z_{ic}(i=1,2,...,N)$. Si algún $z_{i}>z_{ic}$ entonces el vértice $i$ se desploma, es decir que algunos granos del vértice se desplazan hacia vértices vecinos y otros abandonan el sistema. Si el vértice $i$ se desploma entonces $z_{j}\rightarrow z_{j}-\Delta _{ij}$ , para $j=1$ hasta $N$.

La matriz $\Delta$ debe satisfacer las siguientes condiciones:

1. $\Delta _{ii}>0$, para todo $i$.
2. $\Delta _{ij}\leq 0$, para todo $i\neq j$.
3. $\sum _{j=1}^{N}\Delta _{ij}\geq 0$ para todo $i$.

Sin pérdida de generalidad se puede asumir que $z_{ic}=\Delta _{ii}$ para todo $i$. Entonces, si $1\leq z_{i}\leq \Delta _{ii}$ entonces el vértice $i$ es estable.

En este modelo los granos de arena pueden abandonar el sistema a través de un sumidero(un punto cuya altura es fija de valor 0), generalmente en los bordes del grafo. Sobre la base de esto se puede asumir que la matriz $\Delta$ es tal que toda configuración puede llegar a una configuración estable tras un número finito de pasos.

¿Por qué abeliano?

Considerando una configuración inestable en la cual dos vértices, a y b, son críticos, es decir que $z_{a}>z_{ac}yz_{b}>z_{bc}$, el primer desplome en $a$ dejará al vértice $b$ crítico, donde $z_{ic}$ es el valor crítico para el punto $z_{i}$. Después de hacer estable también al vértice $b$ se obtiene una configuración en la cual $z_{i}=z_{i-(\Delta _{ai}+\Delta _{bi})},i=1,2,...,N$. El estado crítico resultante es el mismo al intercambiar el orden de los desplomes, es decir la configuración estable resultante es la misma independientemente del orden de estabilización de los vértices. Haciendo un procedimiento inductivo es fácil observar que esta conmutatividad existe para un número finito de desplomes. Por otro lado, al desplomarse un vértice $a$ inestable inicialmente y luego añadir un grano al vértice $b$, el resultado será igual que añadir un grano de arena en $b$ y luego desplomar el vértice $a$.

Sea una configuración inicial $C$, se define un operador $a_{i},i\in \lbrace 1,2,...,N\rbrace$, tal que $a_{i}C$ es la configuración resultante de poner un nuevo grano en el vértice $i$ y dejar que el grafo se estabilice.

De las dos propiedades anteriores y la definición de $a_{i}$, se tiene que para todas las configuraciones $C$ y todos los $i$ y $j$, $a_{i}a_{j}C=a_{j}a_{i}C$, es decir que el operador $a_{i}$ conmuta. De aquí que se llame modelo abeliano.

La propiedad de ser abeliano es lo que permite caracterizar el modelo ASM de una manera sencilla. Se divide el conjunto de todas las configuraciones posibles en dos clases: configuraciones recurrentes y configuraciones transitorias. Las configuraciones recurrentes son aquellas para las cuales existe un entero positivo $m_{i}$, para cada vértice $i$, tal que:

$a_{i}^{m_{i}}C=C$, para todo $i$.

Se denota el conjunto de todas las configuraciones recurrentes por $R$.

Las configuraciones transitorias son aquellas configuraciones que no son recurrentes. Estas tienen una probabilidad de ocurrir igual a cero.

Es fácil comprobar que $R$ es un grupo con la operación definida como la sobre posición de las dos pilas de arena y su estabilización, que puede expresarse siempre en términos del operador $a$.

Grupo de pilas de arena

Sea $G$ un digrafo con $n$ vértices y un sumidero global $s$. El Laplaciano Reducido $\Delta '$ de $G$ es obtenido borrando de la matriz Laplaciana Δ la fila y la columna correspondientes al sumidero. Observe que al desplomar uno de los vértices no sumidero $v$ se transforma una configuración σ en la configuración $\sigma -{{\Delta }_{v}}'$ , donde ${\Delta }_{v}'$ es la fila del Laplaciano reducido correspondiente a $v$. Se busca una configuración antes del desplome que sea equivalente a la obtenida después del desplome. Se considera el grupo $\mathbb {Z} ^{n-1}/H$, donde $H=\mathbb {Z} ^{n-1}\Delta '$ es la envolvente entera de $\Delta '$.

El grupo de pila de arena es el grupo cociente

$S(G)=\mathbb {Z} ^{n-1}/\mathbb {Z} ^{n-1}\Delta '(G)$

Fig.5. Grupo de pila de arena cíclico de orden 3 (dos configuraciones equivalentes)

Propiedades importantes

Fig.6. El elemento identidad del grupo de pila de arena de la malla cuadrada L × L para diferentes valores de L: L = 128 (arriba izq), 198 (arriba derecha), 243 (abajo izq), y 521 (abajo derecha). El esquema de color es el siguiente: naranja=0 granos, rojo=1 grano, verde=2 granos, y azul=3 granos.

• El orden de $S(G)$ es el determinante de la matriz laplaciana reducida.
• El conjunto de todas las configuraciones recurrentes en G es un grupo abeliano bajo la operación $\left(\sigma ,\sigma '\right)\mapsto \left(\sigma ,\sigma '\right)^{o}$ y es isomorfo vía inclusión al grupo de pila de arena $S(G)$.

El elemento identidad del grupo de pila de arena es de particular interés, i.e. la única configuración recurrente equivalente a todas las 0 configuraciones.

Cálculo de la identidad

Sea $\sigma$ la configuración $2\delta -2$ (combinaciones aritméticas de vectores y escalares se entienden componente a componente). Como $\sigma ^{o}\leq \delta -1$ se tiene que $\sigma -\sigma ^{o}\geq \delta -1$, luego $\sigma -\sigma ^{o}$ es accesible. Como $\sigma -\sigma ^{o}$ es equivalente a $0$, el elemento identidad está dado por $I=\left(\sigma -\sigma ^{o}\right)^{o}$.

Relación con los árboles de expansión

Existe una fuerte conexión entre los grupos de pila de arena y los árboles de expansión. Como el orden del grupo de arena es igual al determinante del laplaciano reducido $\Delta '$ de G y por el Teorema de Kirchhoff se llega a la conclusión de que éste determinante es igual al número de árboles de expansión de G cuya raíz es el sumidero.

Relación con los polinomios de Tutte

Las pilas de arena están relacionadas con el polinomio de Tutte $T\left(x,y\right)$ de G. El número de árboles de expansión de G es igual a $T\left(1,1\right)$. Por el teorema de Merino López, $T\left(1,y\right)$ es igual a la suma de $y^{|\sigma |-m+\delta }$ sobre todas las configuraciones recurrentes $\sigma$, donde $\delta$ es el grado del sumidero global, m es el número de aristas de G, y $|\sigma |$ denota el número de granos en $\sigma$.

El grupo de pilas de arena da interpretaciones algebraicas para varios resultados clásicos de conteo en árboles de expansión. Por ejemplo la Fórmula de Cayley $n^{n-2}$ para el número de árboles de expansión del grafo completo $K_{n}$ se convierte en :

$K\left(K_{n}\right)=\left(\mathbb {Z} _{n}\right)^{n-2}$

Y la fórmula $m^{n-1}n^{m-1}$ para el número de árboles de expansión del grafo bipartito se convierte en :

$K\left(K_{m,n}\right)=\mathbb {Z} _{mn}\times \left(\mathbb {Z} _{m}\right)^{n-2}\times \left(\mathbb {Z} _{n}\right)^{m-2}$

Pilas de arena en $\mathbb {Z} ^{d}$

El replanteamiento del modelo por Dhar permite extender arbitrariamente el ASM a dimensiones superiores a $\mathbb {Z} ^{2}$, trabajando en $\mathbb {Z} ^{d}$, con d un entero positivo. Las demás definiciones permanecen iguales trabajando con vectores en $\mathbb {Z} ^{d}$ como los vértices en el modelo.

Odómetro

El odómetro de una pila de arena σ es la función sobre $V(\sigma )$ definida como:

$u(v)=$ número de veces que se desploma v en el proceso de estabilización.

La configuración estable τ asociada a la pila está dada en términos de σ y $u$ por:

$\tau =\sigma +\Delta u$

En particular, $u$ cumple:

1. $u\geq 0$,
2. $\sigma +\Delta u\leq d-1$

Es sencillo verificar que la regla de desplome del modelo implica un tipo de principio de mínima acción: el odómetro es la mínima función de valor entero que satisface (1) y (2). Es decir que la pila se estabiliza en la mínima cantidad posible de desplomes. Es más, las pilas de arena son también localmente perezosas ya que cada vértice hace la mínima cantidad de trabajo necesario para llegar a la estabilidad.

Algunas propiedades

Dos características fundamentales de ASMs en $\mathbb {Z} ^{d}$ permanecen inexplicadas por teoremas. Una es su invariancia escalar: grandes pilas de arena parecen pequeñas pilas bajo el efecto de un acercamiento. La segunda característica aun inexplicada es su reducción dimensional: cortes d-dimensionales de pilas en $\mathbb {Z} ^{d+1}$ parecen pilas en $\mathbb {Z} ^{d}$, excepto en una región cercana al origen.

Fig.7. Izq: un corte 2-dimensional pasante por el origen de una pila de arena con $n=5(10^{6})$ partículas en $\mathbb {Z} ^{3}$. Der: El ASM de 47465 partículas en $\mathbb {Z} ^{2}$.Coloreado:Izq: Azul=5, Turquesa=4, Amarillo=3, Rojo=2, Gris=1, Blanco=0. Derecha: Azul=3, Turquesa=2, Amarillo=1, Rojo=0.

Pila de arena divisible

Existe un modelo que se basa en el ASM, pero no restringe la cantidad de granos en cada vértice a un valor entero, en cambio, una cantidad continua de masa puede ser subdividida arbitrariamente durante los desplomes. Este modelo es llamado el modelo de Pilas de Arena Divisibles.

El modelo de pilas de arena divisibles tiene un comportamiento completamente diferente al modelo original: si se comienza con una masa $m$ en el origen de $\mathbb {Z} \times \mathbb {Z}$ se obtiene una región $A_{m}$ completamente ocupada y casi circular, bordeada por una región parcialmente cubierta por arena.

Bibliografía

• Bak, Tang, Weisenfeld, «Self-Organized Criticallity: an Explanation of 1/f noise». Physical Review of Letters Vol. 59 No. 4, 1987.Consultado: Mayo de 2015.
• D. Dhar, «Self-Organized Critical State of Sanpile Abelian Automaton Models». Physical Review of Letters vol. 64 num. 14, 1990. Consultado en mayo de 2015.
• F. Redig, «Mathematical Aspects of the Abelian Sandpile Model» 2005. Consultado en mayo de 2015.
• L. Levine, J. Propp, «What is a Sanpile?». University of Nebraska, Notices of the AMS vol.57 num. 8, Septiembre de 2010. Consultado en mayo de 2015.
• J.G. Perlman, BA Thesis: «Sandpiles: a Bridge Between Graphs and Toric Ideals». Mayo de 2009, Reed College. Consultado en mayo de 2015.
• C. Mejía Moreno, «Pilas de Arena Sobre Grafos Dirigidos y Algo de Complejidad». Universidad Industrial de Santander, Revista Integración, vol. 24 No. 2, pag. 101-116, 2006. Consultado en mayo de 2015.

Enlaces externos

• D. Perkinson, Reed College, <<Abelian Sandpile Model>>.
• A.R. Kerns,<<Sanpiles in Graphs>>. Department of Statistics and Computer Science, West Virginia University
• S. Castañeda, <<Pilas de Arena y Grafos de Ramanujan>>, Universidad Industrial de Santander, 2011.
• A. Jarai, University of Bath, Markov Processes Relat. Fields vol.18 pg. 111-156, Octubre de 2011

• Datos: Q4666685
• Multimedia: Abelian sandpile model / Q4666685