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

Speaker: Thomas Vallier, University of Iceland
Title: Majority bootstrap percolation on \(G(n,p)\).

“
Staðsetning: Naustið, Endurmenntun (hér)
Tími: Fimmtudagur 7. maí, klukkan 15:00-16:00.

Ágrip:

Majority bootstrap percolation is a process of spread of „activation“ on a given graph with a given number of initially active nodes \(A(0)\)chosen uniformly at random. At each step those vertices which have more active neighbours than inactive neighbours become active as well.

Sigurður Örn Stefánsson and I consider the process on the random graph \(G(n,p)\)which consists of \(n\)vertices where each pair of vertices is present with probability \(p\)independently of the others.

The process is more involved than the classical bootstrap percolation for which a certain number of active neighbours is required for a vertex to become active. Moreover, the fact that the degree of a vertex, that is, it’s number of neighbours, is random makes the study more difficult than on structures with deterministic neighbourhood.

We study the size \(A^*\)of the final active set depending on the size of the set of initially active vertices for all ranges of \(p=p(n)\). We show that the model exhibits different behaviours for different ranges of \(p\).

I will let you guess the threshold \(A_c(p(n))\) for the process to „percolate“ (that means that the activation spreads to almost all the graph) for the following ranges:

• \(p=oleft(frac{1}{n}right)\)
• \(p gg frac{1}{n}\)
• \(p = frac{c}{n}\)

and will eventually give you the answer.