Fast Construction on a Restricted Budget

Journal article

We introduce a model of a controlled random graph process. In this model, the edges of the complete graph K n $$ {K}_n $$ are ordered randomly and then revealed, one by one, to a player called Builder. He must decide, immediately and irrevocably, whether to purchase each observed edge. The observation time is bounded by parameter t $$ t $$ , and the total budget of purchased edges is bounded by parameter b $$ b $$ . Builder's goal is to devise a strategy that, with high probability, allows him to construct a graph of purchased edges possessing a target graph property 𝒫 , all within the limitations of observation time and total budget. We show the following: (1) Builder has a strategy to achieve k $$ k $$ ‐vertex‐connectivity at the hitting time for this property by purchasing at most c k n $$ {c}_kn $$ edges for an explicit c k < k $$ {c}_k 1 $$ C>1 $$ ; this is optimal in the sense that C $$ C $$ cannot be arbitrarily close to 1. This substantially extends the classical hitting time result for Hamiltonicity due to Ajtai–Komlós–Szemerédi and Bollobás. (3) Builder has a strategy to create a perfect matching by time ( 1 + ε ) n log n / 2 $$ \left(1+\varepsilon \right)n\log n/2 $$ while purchasing at most ( 1 + ε ) n / 2 $$ \left(1+\varepsilon \right)n/2 $$ edges (which is optimal). (4) Builder has a strategy to create a copy of a given k $$ k $$ ‐vertex tree if t ≥ b ≫ max { ( n / t ) k − 2 , 1 } $$ t\ge b\gg \max \left\{{\left(n/t\right)}^{k-2},1\right\} $$ , and this is optimal; (5) For ℓ = 2 k + 1 $$ \ell =2k+1 $$ or ℓ = 2 k + 2 $$ \ell =2k+2 $$ , Builder has a strategy to create a copy of a cycle of length ℓ $$ \ell $$ if b ≫ max { n k + 2 / t k + 1 , n / t } $$ b\gg \max \left\{{n}^{k+2}/{t}^{k+1},n/\sqrt{t}\right\} $$ , and this is optimal.

Authors: Frieze, A; Krivelevich, M; Michaeli, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Random Structures and Algorithms
• Volume: 67
• Issue: 4
• Article number: e70031
• Publication date: 2025-11-29
• Acceptance date: 2025-08-28
• DOI: 10.1002/rsa.70031
• EISSN: 1098-2418
• ISSN: 1042-9832
• Language: English
• Keywords: Hamilton cycle; perfect matching; hitting time; random graph process