Málstofa í stærðfræði
Fyrirlesari: Thomas Vallier, University of Iceland
Titill: Bootstrap percolation on the random graph G_{n,p}
Staðsetning: V-157, VRII
Tími: Mánudagur 15. september, frá 15:00 til 16:00.
Ágrip:
Bootstrap percolation on the random graph G_{n,p} is a process of spread of “activation” on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least r ≥ 2 active neighbours become active as well.
We consider the n vertices with global connections inherited from the structure of the graph G_{n,p}, meaning that any two vertices share an edge with probability p independently of the others.
The presentation is based on the article ”Bootstrap percolation on the random graph G_{n,p}” by Janson, Luczak, Turova and Vallier.
Among other results, they study the size A^* of the final active set depending on the number of vertices active at the origin as a function of n (the number of vertices) and p = p(n) (the probability of connections) which is written a_0(n, p) = a_0. The model exhibits a sharp phase transition: depending on the parameters of the model the final size of activation with a high probability is either n − o(n) or it is o(n).
I will give a pictorial introduction to the model and explain briefly the approach of the authors to derive the threshold for bootstrap percolation on G_{n,p}.Math Colloquium
Speaker: Thomas Vallier, University of Iceland
Title: Bootstrap percolation on the random graph G_{n,p}
Location: V-157, VRII
Time: Monday September 15, at 15:00-16:00.
Abstract:
Bootstrap percolation on the random graph G_{n,p} is a process of spread of “activation” on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least r ≥ 2 active neighbours become active as well.
We consider the n vertices with global connections inherited from the structure of the graph G_{n,p}, meaning that any two vertices share an edge with probability p independently of the others.
The presentation is based on the article ”Bootstrap percolation on the random graph G_{n,p}” by Janson, Luczak, Turova and Vallier.
Among other results, they study the size A^* of the final active set depending on the number of vertices active at the origin as a function of n (the number of vertices) and p = p(n) (the probability of connections) which is written a_0(n, p) = a_0. The model exhibits a sharp phase transition: depending on the parameters of the model the final size of activation with a high probability is either n − o(n) or it is o(n).
I will give a pictorial introduction to the model and explain briefly the approach of the authors to derive the threshold for bootstrap percolation on G_{n,p}.