论文标题
在随机扰动的挖掘中的定向循环上
On oriented cycles in randomly perturbed digraphs
论文作者
论文摘要
2003年，Bohman，Frieze和Martin启动了随机扰动的图和挖掘的研究。对于Digraphs，他们表明，每$α> 0 $，都存在一个恒定的$ c $，以至于每$ n $ n $ vertex digraph至少至少半学位，如果有人添加$ cn $ cn $随机边缘，则几乎肯定地毫无疑问地将产生的挖掘物包含一个始终如一的挖掘物。我们概括了它们的结果，表明该定理的假设实际上几乎可以肯定地确保同时存在每个可能长度的周期的每个方向。此外，我们证明，当考虑一个不包含大量indegree $ 1 $的周期方向时，我们可以将最低半学位条件放松至最低总学位条件。我们的证明利用了蒙哥马利吸收方法的一种变体。
In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $α>0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $αn$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$. Our proofs make use of a variant of an absorbing method of Montgomery.
