For a better experience, click the Compatibility Mode icon above to turn off Compatibility Mode, which is only for viewing older websites.

Math Colloquium: Bootstrap Percolation on Uniform Attachment Graphs

Wednesday, November 14, 2018

3:00 PM-4:00 PM

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.

Contact Information

Georgi Medvedev

Remind me about this event. Notify me if this event changes. Add this event to my personal calendar.


Papadakis Integrated Sciences Building, Room 108, 3245 Chestnut Street, Philadelphia, PA 19104


  • Everyone