Fast construction on a restricted budget

arXiv2207.07251MaRDI QIDQ6405044FDOQ6405044

Alan Frieze, Michael Krivelevich, Peleg Michaeli

Publication date: 14 July 2022

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 $mathcalP$, 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+varepsilon)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'os--Szemer'edi and Bollob'as. (c) Builder has a strategy to create a perfect matching by time $(1+varepsilon)nlogn/2$ while purchasing at most $(1+varepsilon)n/2$ edges (which is optimal). (d) Builder has a strategy to create a copy of a given $k$-vertex tree if $tgebggmax(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 $bggmax{n}^{k+2}/t^{k+1},n/sqrtt$, and this is optimal.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Eulerian and Hamiltonian graphs (05C45)

This page was built for publication: Fast construction on a restricted budget

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405044)