论文标题
预算有限的快速建设
Fast construction on a restricted budget
论文作者
论文摘要
我们引入了一个受控的随机图过程的模型。在此模型中，完整图$ k_n $的边缘被随机订购，然后一个一个一个一个一个称为Builder的播放器。他必须立即决定是否购买每个观察到的边缘。观察时间由参数$ t $界定，并且购买的边缘的总预算由参数$ b $界定。 Builder的目标是制定一种策略，该策略具有很高的可能性，使他能够构建具有目标图属性$ \ Mathcal {P} $的购买边缘的图表，所有这些都属于观察时间和总预算的限制。我们显示以下内容：（a）建筑商有一种策略，可以通过购买$ c_kn $ edges以明显的$ c_k <k $购买$ k $ vertex连接性。以及在最低度$ k $的门槛之后，通过购买$（1+ \ Varepsilon）kn/2 $边缘（最佳）来实现最低度$ k $（稍微）的策略。 （b）建筑商的策略是在最多购买$ cn $边缘以绝对常数$ c> 1 $购买的汉密尔顿时期创建汉密尔顿周期的策略；从某种意义上说，这是最佳的，因为$ c $不能任意接近$ 1 $。这大大延长了由于Ajtai-komlós--szemerédi和Bollobás而引起的Hamiltonicity的经典打击时间。 （c）建筑商的策略可以在时间$ $（1+ \ varepsilon）N \ log {n}/2 $时创建完美的匹配，而最多购买$（1+ \ varepsilon）n/2 $ edges（最佳）。 （d）建筑商的策略是创建给定的$ K $ -VERTEX树的副本，如果$ t \ ge b \ gg \ gg \ max \ {（n/t）^{k-2}，1 \} $，这是最佳的； （e）对于$ \ ell = 2k+1 $或$ \ ell = 2k+2 $，建筑商具有创建长度周期$ \ ell $的副本，如果$ \ ell $如果$ b \ gg \ gg \ gg \ max \ {n^{k+2}/t}/t}/t^{k+1}，n/\ sqrt {t} $
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_kn$ 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ós--Szemerédi and Bollobás. (c) Builder has a strategy to create a perfect matching by time $(1+\varepsilon)n\log{n}/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 $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.
