Sublinear graph-bootstrap running-time conjecture

Let HH be a graph, and let MH(n)M_H(n) denote the maximum running time of the HH-bootstrap process over all starting graphs on nn vertices. Sublinear running-time conjecture. Every graph HH with

MH(n)=o(n)M_H(n)=o(n)

satisfies either

MH(n)=O(1)M_H(n)=O(1)

or

MH(n)=Θ(logn).M_H(n)=\Theta(\log n).

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

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.