Subquadratic maximum running time conjecture for graph bootstrap percolation
For , let denote the maximum number of time steps for which the -bootstrap process on vertices can run before stabilizing. Subquadratic running-time conjecture. For all ,
The exact maximum running time is unknown for , and even proving any non-trivial upper bound on 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.