Subquadratic maximum running time conjecture for graph bootstrap percolation

For r5r\geqslant 5, let Mr(n)M_r(n) denote the maximum number of time steps for which the KrK_r-bootstrap process on nn vertices can run before stabilizing. Subquadratic running-time conjecture. For all r5r\geqslant 5,

Mr(n)=o(n2).M_r(n)=o(n^2).

The exact maximum running time is unknown for r5r\geqslant 5, and even proving any non-trivial upper bound on Mr(n)M_r(n) is open. The conjecture gives a weaker proposed bound than the heuristic estimate discussed immediately beforehand.

Sources & referencesView supporting material

Primary source

Béla Bollobás, Michał Przykucki, Oliver Riordan and Julian Sahasrabudhe, “On the maximum running time in graph bootstrap percolation”, arXiv:1510.07096 (2015).

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.