Seminars & Colloquia Calendar
Bootstrap percolation on uniform attachment graphs
Huseyin Acan, Drexel
Location: Hill 705
Date & time: Monday, 29 October 2018 at 2:00PM - 3:00PM
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, which is a random graph on the vertex set [n], where each vertex v makes k selections from [v-1] uniformly and independently, and these selections determine the edge set. We start the process with a random S and find a threshold value of |S| for the spread of infection to all vertices.
Joint work with Boris Pittel.