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 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 , and the total budget of purchased edges is bounded by parameter . 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 ‐vertex‐connectivity at the hitting time for this property by purchasing at most edges for an explicit ; and a strategy to achieve minimum degree (slightly) after the threshold for minimum degree by purchasing at most edges (which is optimal). (2) Builder has a strategy to create a Hamilton cycle at the hitting time for Hamiltonicity by purchasing at most edges for an absolute constant ; this is optimal in the sense that 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 while purchasing at most edges (which is optimal). (4) Builder has a strategy to create a copy of a given ‐vertex tree if , and this is optimal; (5) For or , Builder has a strategy to create a copy of a cycle of length if , and this is optimal.