Fast construction on a restricted budget

Abstract

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/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. (c) Builder has a strategy to create a perfect matching by time $(1+\epsilon )n\log n/2$ while purchasing at most $(1+\epsilon )n/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/t{)}^{k-2},1\}$, and this is optimal; (e) For $\ell =2k+1$ or $\ell =2k+2$, Builder has a strategy to create a copy of a cycle of length $\ell$ if $b\gg \max \{n^{k+2}/t^{k+1},n/\sqrt{t}\}$, and this is optimal.

31 pages, 3 figures; minor changes and corrections