Subquadratic maximum running time conjecture for graph bootstrap percolation

About 11 years old · traced to

For r⩾5r\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 r⩾5r\geqslant 5,

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

The exact maximum running time is unknown for r⩾5r\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.

References

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.