4/27/18 10:00  Frederik Garbe (Czech Academy of Sciences, MI): Contagious sets in degreeproportional bootstrap percolation
Description:  We study the following bootstrap percolation process: given a connected graph G, we infect an initial set A of vertices, and in each step a vertex v becomes infected if at least a ρproportion of its neighbours are infected. 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 ρ between 0 and 1, every connected graph G on n vertices has a contagious set of size less than 2ρ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 result is bestpossible and improves previous results of Chang, Chang and Lyuu, and Gentner and Rautenbach. We also provide a stronger bound in the case of graphs of girth at least five. Both proofs exploit the structure of a minimal counterexample in a randomised fashion. This is joint work with Andrew McDowell and Richard Mycroft. 
www:  http://uivty.cs.cas.cz/ExtrA/seminar.html 
