Subquadratic maximum running time conjecture for graph bootstrap percolation
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.