The tree conjecture for maximum running time

For a tree TT on tt vertices, define

M(t):=max{lim supnMT(n):T is a t-vertex tree}.M^*(t):=\max\left\{\limsup_{n\rightarrow\infty}M_T(n):T\text{ is a $t$-vertex tree}\right\}.

Tree conjecture. For all tNt\in\mathbb N,

M(t)=t1.M^*(t)=t-1.

The known upper bound is quadratic in tt, while stars give the lower bound M(t)t1M^*(t)\geq t-1. The conjecture asserts that stars attain the largest asymptotic maximum running time among tt-vertex trees.

Sources & referencesView supporting material

Primary source

David Fabian, Patrick Morris and Tibor Szabó, “Graph bootstrap percolation – a discovery of slowness”, arXiv:2602.12736 (2026).

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.