The budget-threshold conjecture for constructing a copy of
Let be the number of vertices, let denote the set of admissible times, let be a time parameter, and let be a budget parameter. A -strategy is a strategy in the budget-constrained random graph process, and is the graph produced by time . Write when as , and say that an event holds a.a.s. when it holds with probability tending to . The budget-threshold conjecture for . For all , if
then for any -strategy, a.a.s. does not contain a copy of . The authors explain that their methods give non-trivial bounds for 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
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.