Bootstrap percolation on infinite trees
|
Tue, 19/02 14:30 |
Karen Johannson (Bristol) |
Combinatorial Theory Seminar  |
L3 |
While usual percolation concerns the study of the connected components of
random subgraphs of an infinite graph, bootstrap percolation is a type of
cellular automaton, acting on the vertices of a graph which are in one of
two states: `healthy' or `infected'. For any positive integer  , the
-neighbour bootstrap process is the following update rule for the
states of vertices: infected vertices remain infected forever and each
healthy vertex with at least infected neighbours becomes itself
infected. These updates occur simultaneously and are repeated at discrete
time intervals. Percolation is said to occur if all vertices are
eventually infected.
As it is often difficult to determine precisely which configurations of
initially infected vertices percolate, one often considers a random case,
with each vertex infected independently with a fixed probability  . For
an infinite graph, of interest are the values of for which the
probability of percolation is positive. I will give some of the history
of this problem for regular trees and present some new results for
bootstrap percolation on certain classes of randomly generated trees:
Galton–Watson trees. |
|||