Linear running time and self-closure for theta-graph bootstrap percolation
For every fixed theta graph H = Θ(a, b, c) with path lengths a, b, c ≥ 2, we prove that the maximum stabilization time of the ordinary synchronous H-bootstrap process on arbitrary n-vertex graphs is Θ_H(n). The matching lower bound is due to Fabian, Morris and Szabó. We prove the upper bound by combining structural properties of theta graphs with acceleration criteria. For non-bipartite theta graphs, cycle reflections and rearrangements of spanning copies establish complete self-closure, allowing us to apply the acceleration theorem of Fabian, Morris and Szabó. For bipartite rules with all path lengths at least three, we use an attached-path criterion together with a bound on permutation-group orbits. Bipartite rules with a path of length two are handled separately. We also classify all theta self-closures: complete for non-bipartite rules, complete bipartite on the natural color classes for unequal bipartite lengths, and unchanged for equal lengths. The seed argument extends to any fixed family of at least three internally vertex-disjoint paths between two common endpoints, with all lengths at least three and of the same parity.
Authors
- Haimin Zhou
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-15
- DOI
- https://doi.org/10.5281/zenodo.24227361
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint