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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Linear running time and self-closure for theta-graph bootstrap percolation

Haimin Zhou
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Linear running time and self-closure for theta-graph bootstrap percolation

Haimin Zhou
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon