Sublinear graph-bootstrap running-time conjecture
Sublinear graph-bootstrap running-time conjecture
Let be a graph, and let denote the maximum running time of the -bootstrap process over all starting graphs on vertices. Sublinear running-time conjecture. Every graph with
satisfies either
or
A negative answer to the preceding degree-one-vertex question would motivate this dichotomy, asserting that below linear running times only bounded and logarithmic orders occur. The source does not state a resolution of this conjecture.
Sources & referencesView supporting material
Primary source
David Fabian, Patrick Morris and Tibor Szabó, “Slow graph bootstrap percolation II: Accelerating properties”, arXiv:2311.18786 (2024).
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.