Contagious sets in a degree-proportional bootstrap percolation process

Add to your list(s) Download to your calendar using vCal

• Fred Garbe (University of Birmingham)
• Tuesday 24 October 2017, 15:00-16:00
• Watson LTA.

If you have a question about this talk, please contact Guillem Perarnau.

We study the following bootstrap percolation process: given a connected graph G, we infect an initial set of vertices A, and in each step a vertex v becomes infected if at least a \rho-proportion of its neighbours are infected (where \rho is a fixed constant). Once infected, a vertex remains infected forever. A set A which infects the whole graph is called a contagious set. It is natural to ask for the minimal size of a contagious set.

Our main result states that for every \rho between 0 and 1, every connected graph G on n vertices has a contagious set of size less than 2\rho n or a contagious set of size 1 (note that allowing the latter possibility is necessary since every contagious set has size at least one). This improves previous results of Chang and of Chang and Lyuu, who established the analogous bounds with 5.83 \rho n and 4.92 \rho n respectively in place of 2 \rho n, and also improves a recent result of Gentner and Rautenbach, who proved the analogous result with (2+\eps)\rho n in place of 2 \rho n for the special case when G has girth at least five and \rho is sufficiently small compared to \eps. Moreover, a simple construction shows that our theorem is best-possible in the sense that the bound 2\rho n cannot be replaced by C \rho n for any C < 2.

This is joint work with Andrew McDowell and Richard Mycroft.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTA

Note that ex-directory lists are not shown.