Event Description
Huseyin Acan, PhD, Drexel University
Abstract: Bootstrap percolation is a process defined on a graph, which
starts with a set S of initially infected vertices. Afterward, at each step, an
uninfected vertex with at least r infected neighbors becomes infected and stays
infected forever. If r=1, then all vertices in a connected graph get infected
at some point as long as there is at least one infected vertex initially.
However, for r>1, the final set of infected vertices depends on the graph
and S.
We study bootstrap percolation on a uniform attachment
graph. This is a random graph on the vertex set {1,…,n}, where each vertex v
makes k selections from {1,…,v-1} uniformly and independently, and these
selections determine the edge set. We start the process with a random S. Our
main interest is finding a threshold value of the size of S for the spread of
infection to all vertices. I will talk about the upper and lower bounds we have
on this threshold, which are not far from each other.
Joint
work with Boris Pittel. |
