The maximum-running-time comparison conjecture for infection rules

Let HH be an infection rule, let MH(n)M_H(n) be the maximum running time over all starting graphs on nn vertices, and let

MH(n):=max{τH(G):G is an n-vertex H-percolating graph}.M'_H(n):=\max\{\tau_H(G): G\text{ is an $n$-vertex $H$-percolating graph}\}.

Maximum-running-time comparison conjecture. For all infection rules HH,

MH(n)=Θ(MH(n)).M_H(n)=\Theta(M'_H(n)).

The theorem preceding this conjecture gives a comparison for (2,1)(2,1)-inseparable infection rules up to a constant-factor change in the number of vertices, but the general comparison remains open.

Sources & referencesView supporting material

Primary source

David Fabian, Patrick Morris and Tibor Szabó, “Graph bootstrap percolation – a discovery of slowness”, arXiv:2602.12736 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.