2023/11/30 by David M. Fabian, Patrick Morris, Fabian, David +3
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2311.18786
openalex publication_date 2023/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
For a graph H and an n-vertex graph G, the H-bootstrap process on G is the process which starts with G and, at every time step, adds any missing edges on the vertices of G that complete a copy of H. This process eventually stabilises and we are interested in the extremal question raised by Bollobás of determining the maximum running time (number of time steps before stabilising) of this process over all possible choices of n-vertex graph G. In this paper, we initiate a systematic study of the asymptotics of this parameter, denoted MH(n), and its dependence on properties of the graph H. Our focus is on H which define relatively fast bootstrap processes, that is, with MH(n) being at most linear in n. We study the graph class of trees, showing that one can bound MT(n) by a quadratic function in v(T) for all trees T and all n. We then go on to explore the relationship between the running time of the H-process and the minimum vertex degree and connectivity of H.