Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs

Abstract

Bootstrap percolation in graphs, also known as bond percolation, originates as a method to study ferromagnetism in 2D and 3D lattices, though it has more recently been used to model other more complicated networks of physical, biological, and sociological natures. Percolation theory has widespread applications including studying the spread of disease and information through social networks, testing the robustness of the internet and power grids, protecting ecosystems in the face of losing keystone species, understanding the development of neuronal cultures, and analyzing the role of dynamical arrest in forming complex condensed states of matter. Weak saturation and edge bootstrap percolation are two variations on this process, both of which measure the presence of certain subgraphs H inside of a given graph.

A graph G is weakly H-saturated if one can obtain K_n by adding one edge to G at a time, where each additional edge creates at least one new copy of H. The minimum number of edges needed for a weakly H-saturated graph G on n vertices is known as the weak saturation number of H, written wsat(n,H). A graph G is minimum weakly saturated if wsat(n,G)=|E(G)|-1 for some n.

We explore classes of minimum weakly saturated graphs and their connection to the H-bootstrap percolation process, as well as weak saturation in a more general setting than the complete graph.