On constructing small subgraphs in the budget-constrained random graph process

Sylwia Antoniuk, Alberto Espuny Díaz, Kalina Petrova, Miloš Stojaković

arXivarxiv/2602.18325Feb 20, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.18325
curl -X POST /api/v1/records/arxiv/2602.18325/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.18325/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'