The tree conjecture for maximum running time

For a tree TT on tt vertices, define

M∗(t):=max⁡{lim sup⁡n→∞MT(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 t∈Nt\in\mathbb N,

M∗(t)=t−1.M^*(t)=t-1.

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

References

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.