The budget-threshold conjecture for constructing a copy of
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.