论文标题
有效地建造汉密尔顿周期和完美的匹配
Constructing Hamilton cycles and perfect matchings efficiently
论文作者
论文摘要
令$ε> 0 $。我们考虑在以下受控的随机图过程中构建具有$（1+ε）n $边缘的哈密顿图的问题。从$ [n] $上的空图开始，在每回合中，都会呈现一组$ k = k（n）$边缘，从失踪者（或从尚未呈现的$）中随机选择均匀地选择，我们最多要求我们选择其中一个并将其添加到当前图中。我们表明，在此过程中，人们可以在$（1+ε）（1+ε）（1+（\ log n）/2k）n $ rounds w.h.p.中构建最多使用$（1+ε）n $边缘的汉密尔顿图。 $ k = 1 $表示W.H.P.一个人可以通过在线形式出现$（1+ε）n $边缘来构建汉密尔顿图，因为它们沿着第一个$（0.5+ε）n \ log n $ n $步骤出现在随机图过程中，这反驳了Frieze，Krivelevich和Michaeli的猜想。 $ k =θ（\ log n）$表示相应的ACHLIOPTAS过程的Hamiltonity阈值最多为$（1+ε）（1+（\ log n）/2k）n $。这匹配$（1-ε）（1+（\ log n）/2k）n $下降，这是由于Krivelevich，Lubetzky和Sudakov引起的，并解决了确定Achlioptas进程的Hamiltonity threshold的问题，并使用$ K =θ（\ log log n）$。 我们还表明，在上述过程中，W.H.P.一个人可以构建一个覆盖大小$ \ lfloor v（g）/2）\ rfloor $的图形$ g $，带有$（0.5+ε）n $边缘，在$（1+ε）（0.5+（\ log n）/2k）n $ n $ n $ n $ n $ n $ n $ nods。 我们的证明依赖于强大的Hamiltonity属性，即二项式随机图的强大$ 4 $ core，我们用作黑盒。该属性允许它吸收覆盖较强$ 4 $ core的顶点的路径。
Let $ε>0$. We consider the problem of constructing a Hamiltonian graph with $(1+ε)n$ edges in the following controlled random graph process. Starting with the empty graph on $[n]$, at each round a set of $K=K(n)$ edges is presented, chosen uniformly at random from the missing ones (or from the ones that have not been presented yet), and we are asked to choose at most one of them and add it to the current graph. We show that in this process one can build a Hamiltonian graph with at most $(1+ε)n$ edges in $(1+ε)(1+(\log n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian graph by choosing $(1+ε)n$ edges in an on-line fashion as they appear along the first $(0.5+ε)n\log n$ steps of the random graph process, this refutes a conjecture of Frieze, Krivelevich and Michaeli. The case $K=Θ(\log n)$ implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most $(1+ε)(1+(\log n)/2K) n$. This matches the $(1-ε)(1+(\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky and Sudakov and resolves the problem of determining the Hamiltonicity threshold of the Achlioptas process with $K=Θ(\log n)$. We also show that in the above process w.h.p. one can construct a graph $G$ that spans a matching of size $\lfloor V(G)/2) \rfloor$, with $(0.5+ε)n$ edges, within $(1+ε)(0.5+(\log n)/2K) n$ rounds. Our proof relies on a robust Hamiltonicity property of the strong $4$-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong $4$-core into a cycle.
