Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs
Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs
复制标题
随机扰动有向图和超图中的循环和匹配
DOI：
10.1017/s0963548316000079
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Michael Krivelevich;Matthew Kwan;B. Sudakov
我们给出的几个结果表明，不同的离散结构通常在适度的随机扰动后获得某些生成子结构(特别是哈密尔顿环)。首先，我们证明了在稠密k-一致超图上线性地添加许多随机边可以保证(渐近地几乎确定)完美匹配或松散哈密尔顿圈的存在。证明涉及到Szemerédi正则性引理的一个有趣的应用，这可能是独立有用的。接下来，我们证明了具有某些强扩张性质的有向图是泛圈的，并利用这一点证明了将线性数量的随机边相加通常会使稠密有向图成为泛圈。最后，我们证明了在竞赛中扰动一定数量(最小度相关)的随机边通常确保存在多条边不相交的哈密尔顿圈。我们所有的结果都很紧张。
We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.
托马森关于高度关联锦标赛中汉密尔顿循环的猜想的证明
影响因子：
1.8
作者：
Kühn D
通讯作者：
Kühn D