﻿

## Thomas Vallier (03/02/17)

Anders Claesson, janúar 31, 2017

Málstofa í stærðfræði

### Titill: Discussion on Bootstrap percolation on a random graph coupled with a lattice

Staðsetning: Tg-227 (Tæknigarður, 2. hæð)
Tími: Föstudagur 3. febrúar kl. 13:20

### Ágrip:

will give an informal seminar on the paper by Janson, Kozma, Ruszinko and Sokolov. In the paper „Bootstrap percolation on a random graph coupled with a lattice“, the authors consider a set of vertices $$N$$x$$N$$ on a lattice. On top of that, every vertex shares a link with any other vertex with a probability inversely proportional to there block distance and independently of any other link. That means for two vertices $$u$$ and $$v$$ at distance $$d P(u,v) = c/(Nd)$$ where $$c$$ is a constant.

The authors derive the diameter of the of the graph in a very elegant way which we will unfortunately not focus on. Instead, we will discuss the other part which deals with the following cellular automaton with threshold $$k$$:

1. Start with a set of active (or infected depending on the terminology you want to use) vertices at time $$0$$, $$A(0)$$.

2. Any vertex which has at least k active vertices in its closed neighbourhood (including itself) at time $$t$$ is set as active at time $$t+1$$. Notice that two vertices are neighbours if they share an edge in common either from the lattice or from the random connections.

Otherwise, if it has less than $$k$$ active vertices in the closed neighbourhood then the vertex is set as inactive at time $$t+1$$.

3. We repeat the process over time.

The authors study the „mean field approximation“ which simplifies the problem by averaging the links over space. Under this assumption, the problem simplifies into a 1-dimensional dynamical system. The authors derive the fixed points of the dynamical system for
$$k \leq 3$$.

There are good indications that the process becomes more interesting (that means more complicated) for larger $$k$$. I would like to discuss that subject with you all if you’re curious about it. Anyone who’s interested in talking and sharing ideas is very welcome.