Spanning cycles in random directed graphs
Spanning cycles in random directed graphs
复制标题
随机有向图中的跨越循环
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
R. Montgomery
中科院分区：
文献类型：
--
作者：
R. Montgomery
我们证明，在几乎每个顶点随机有向图过程中，每个可能的顶点定向圈的副本将严格出现在有向汉密尔顿圈之前，当然除了有向圈本身。此外，给定一个任意顶点定向的圈，我们确定了它在二项式随机有向图中出现的尖锐阈值。这些结果以强有力的形式证实了Ferber和Long的猜想。
We show that, in almost every ‐vertex random directed graph process, a copy of every possible ‐vertex oriented cycle will appear strictly before a directed Hamilton cycle does, except of course for the directed cycle itself. Furthermore, given an arbitrary ‐vertex oriented cycle, we determine the sharp threshold for its appearance in the binomial random directed graph. These results confirm, in a strong form, a conjecture of Ferber and Long.