Fast construction on a restricted budget

We introduce a model of a controlled random graph process. In this model, the edges of the complete graph $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$, and the total budget of purchased edges is bounded by parameter $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 $\mathcal{P}$, all within the limitations of observation time and total budget. We show the following: (a) Builder has a strategy to achieve $k$-vertex-connectivity at the hitting time for this property by purchasing at most $c_{k}n$ edges for an explicit $c_k<k$; and a strategy to achieve minimum degree $k$ (slightly) after the threshold for minimum degree $k$ by purchasing at most $(1+\epsilon )kn\mathrm{/}2$ edges (which is optimal). (b) Builder has a strategy to create a Hamilton cycle at the hitting time for Hamiltonicity by purchasing at most $Cn$ edges for an absolute constant $C>1$; this is optimal in the sense that $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. © Builder has a strategy to create a perfect matching by time $(1+\epsilon )n\log n\mathrm{/}2$ while purchasing at most $(1+\epsilon )n\mathrm{/}2$ edges (which is optimal). (d) Builder has a strategy to create a copy of a given $k$-vertex tree if $t\ge b\gg \max \{(n\mathrm{/}t{)}^{k-2},1\}$, and this is optimal; (e) For $\mathrm{\ell }=2k+1$ or $\mathrm{\ell }=2k+2$, Builder has a strategy to create a copy of a cycle of length $\mathrm{\ell }$ if $b\gg \max \{n^{k+2}\mathrm{/}{t}^{k+1},n\mathrm{/}\sqrt{t}\}$, and this is optimal.