Nadcházející semináře

  • Tommaso Moraschini: Abstract consequence relations II: the categorial perspective

    25.4.2018 10:00 @ Applied Mathematical Logic

  • Frederik Garbe (Czech Academy of Sciences, MI): Contagious sets in degree-proportional bootstrap percolation

    27.4.2018 10:00 @ Applied Mathematical Logic

    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 best-possible 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.