2019/09/10 by Alexandra Wesolek, Wesolek, Alexandra
Mathematics · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1909.04649
The r-neighbour bootstrap process describes an infection process on a graph, where we start with a set of initially infected vertices and an uninfected vertex becomes infected as soon as it has r infected neighbours. An inital set of infected vertices is called percolating if at the end of the bootstrap process all vertices are infected. We give Ore-type conditions that guarantee the existence of a small percolating set of size l≤ 2r-2 if the number of vertices n of our graph is sufficiently large: if l≥ r and satisfies 2r ≥ l+2 \lfloor √(2(l-r)+0.25)+2.5 \rfloor-1 then there exists a percolating set of size l for every graph in which any two non-adjacent vertices x and y satisfy deg(x)+deg(y) ≥ n+4r-2l-2\lfloor√(2(l-r)+0.25)+2.5 \rfloor-1 and if l is larger with l≤ 2r-2 there exists a percolating set of size l if deg(x)+deg(y) ≥ n+2r-l-2. Our results extend the work of Gunderson, who showed that a graph with minimum degree \lfloor n/2 \rfloor+r-3 has a percolating set of size r ≥ 4. We also give bounds for arbitrarily large l in the minimum degree setting.