The edge-deletion extremal upper-bound conjecture

Less than 1 year old · traced to

Let HH be an infection rule with at least three edges, let MH(n)M_H(n) denote the maximum running time of the HH-process, and let ex⁡(n,H−e)\operatorname{ex}(n,H-e) be the Turán extremal number of H−eH-e for an edge e∈E(H)e\in E(H). Edge-deletion extremal conjecture. For every infection rule HH with at least three edges,

MH(n)≤O(min⁡e∈E(H)ex⁡(n,H−e)).M_H(n)\leq O\left(\min_{e\in E(H)}\operatorname{ex}(n,H-e)\right).

This conjecture proposes a general extremal upper bound for maximum running times, beyond the bipartite setting. It remains open, as the paper states the claim as a belief following the discussion of bipartite extremal bounds.

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.