﻿

## Thomas Vallier (07/05/15)

Benedikt Magnússon, maí 4, 2015

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=o\left(\frac{1}{n}\right)$$
• $$p \gg \frac{1}{n}$$
• $$p = \frac{c}{n}$$

and will eventually give you the answer.