{"id":"arxiv/2602.18325","url":"https://arxiv.org/abs/2602.18325","tags":["math.CO"],"score":0,"title":"On constructing small subgraphs in the budget-constrained random graph process","domain":"math.CO","source":"arxiv","authors":["Sylwia Antoniuk","Alberto Espuny Díaz","Kalina Petrova","Miloš Stojaković"],"reviews":0,"subject":"math.CO","summary":"Consider the budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli, where each time an edge is offered through the (standard) random graph process we must irrevocably decide whether to \"purchase\" this edge or not, with our goal being to construct a graph which satisfies some property within a given time $t$ and while purchasing at most $b$ edges. We consider the problem of constructing graphs containing certain fixed small subgraphs. We provide an optimal strategy for building a graph which contains a copy of $K_4$, showing that budget…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-20","reactions":{}}