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/g0f/g\to 0 as nn\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.

Sources & referencesView supporting material

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.