2018/06/07 by Natasha Morrison, Jonathan A. Noel, Morrison, Natasha +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.1806.02903
arxiv created 2020/10/07 · arxiv updated 2020/10/08
Given a hypergraph H, the H-bootstrap process starts with an initial set of infected vertices of H and, at each step, a healthy vertex v becomes infected if there exists a hyperedge of H in which v is the unique healthy vertex. We say that the set of initially infected vertices percolates if every vertex of H is eventually infected. We show that this process exhibits a sharp threshold when H is a hypergraph obtained by randomly sampling hyperedges from an approximately d-regular r-uniform hypergraph satisfying some mild degree and codegree conditions; this confirms a conjecture of Morris. As a corollary, we obtain a sharp threshold for a variant of the graph bootstrap process for strictly 2-balanced graphs which generalises a result of Korándi, Peled and Sudakov. Our approach involves an application of the differential equations method.