The budget-threshold conjecture for constructing a copy of K5K_5

Let nn be the number of vertices, let [M][M] denote the set of admissible times, let tt be a time parameter, and let bb be a budget parameter. A (t,b)(t,b)-strategy is a strategy in the budget-constrained random graph process, and BtB_t is the graph produced by time tt. Write f=o(g)f=o(g) when f/g→0f/g\to 0 as n→∞n\to\infty, and say that an event holds a.a.s. when it holds with probability tending to 11. The budget-threshold conjecture for K5K_5. For all t∈[M]t\in[M], if

t=o(n3/2)orb=o(max⁡{n12t7,(n2t)5/3}),t=o\left(n^{3/2}\right)\qquad\text{or}\qquad b=o\left(\max\left\{\frac{n^{12}}{t^{7}},\left(\frac{n^{2}}{t}\right)^{5/3}\right\}\right),

then for any (t,b)(t,b)-strategy, a.a.s. BtB_t does not contain a copy of K5K_5. The authors explain that their methods give non-trivial bounds for K5K_5 but do not yet establish tight results for larger cliques; they believe the corresponding upper-bound behaviour should be correct, so the precise budget threshold remains open.

References

Primary source

Sylwia Antoniuk, Alberto Espuny Díaz, Kalina Petrova and Miloš Stojaković, “On constructing small subgraphs in the budget-constrained random graph process”, arXiv:2602.18325 (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.