Huseyin Acan, Rutgers 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, 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