Thomas Vallier (03/02/17)

Anders Claesson, janúar 31, 2017

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

Fyrirlesari: Thomas Vallier, University of Iceland

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


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.