Slow graph bootstrap percolation III: Chain constructions
David Fabian 1,∗, Patrick Morris 2,†, Tibor Szabó 3,‡ · 2025
Read Slow graph bootstrap percolation III: Chain constructions by David Fabian 1,∗, Patrick Morris 2,†, Tibor Szabó 3,‡ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-03835.txt.
Introduction
David Fabian, Patrick Morris, and Tibor Szabó wrote this 2025 mathematics paper on how slowly an infection-like process can spread through a graph. In bootstrap percolation, edges or vertices join the spread once enough neighbors are already in. The key measure is the longest time the process can take to settle on a graph of a given size.
The authors build a general method based on chains of smaller graphs. They vary the method to set lower bounds for many graph types, from dense graphs to random and two-sided complete graphs. A main question is whether the longest time grows nearly like the square of the size. Their bounds link the problem to additive combinatorics and to a classic theorem on triples, and matching upper bounds round out the picture.
Catalog record
| CREATOR | David Fabian 1,∗, Patrick Morris 2,†, Tibor Szabó 3,‡ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 221 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-03835