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

CREATORDavid Fabian 1,∗, Patrick Morris 2,†, Tibor Szabó 3,‡
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE221 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-03835

Browse the full library · About the Tower of Babel