Packing hamilton cycles in random and pseudo‐random hypergraphs
Packing hamilton cycles in random and pseudo‐random hypergraphs
复制标题
在随机和伪随机超图中包装哈密尔顿循环
DOI：
10.1002/rsa.20396
复制
发表时间：
2010
影响因子：
1
通讯作者：
Michael Krivelevich
中科院分区：
文献类型：
--
作者：
A. Frieze;Michael Krivelevich
我们说一个k一致超图C是一个汉密尔顿型圈，对于某个1 ≤ k ≤ k，如果存在C的顶点的循环序，使得每个边由k个连续顶点组成，并且对于C中的每对连续边Ei-1，Ei（在边的自然序中），我们有|Ei‐1 / Ei| = 0。我们证明了当k/2 <n ≤ k时，随机k-一致超图H（n，p，k）（p（n））的几乎所有边都有很高的概率可以分解为边不交型双汉密尔顿圈.对于k = k/2给出了一个稍弱的结果。我们还给出了一个伪随机k一致超图的几乎所有边都分解为n型汉密尔顿圈的充分条件，其中k/2 ≤ n ≤ k.对于k = k的情况，这些结果表明，几乎所有相应的随机和伪随机超图的边都可以用不相交的完美匹配填充。© 2012 Wiley Periodicals，Inc.随机结构算法，2012
We say that a k ‐uniform hypergraph C is a Hamilton cycle of type ℓ, for some 1 ≤ ℓ ≤ k, if there exists a cyclic ordering of the vertices of C such that every edge consists of k consecutive vertices and for every pair of consecutive edges Ei‐1,Ei in C (in the natural ordering of the edges) we have |Ei‐1 / Ei| = ℓ. We prove that for k/2 < ℓ ≤ k, with high probability almost all edges of the random k ‐uniform hypergraph H(n,p,k) with p(n) ≫ log 2n/n can be decomposed into edge‐disjoint type ℓ Hamilton cycles. A slightly weaker result is given for ℓ = k/2. We also provide sufficient conditions for decomposing almost all edges of a pseudo‐random k ‐uniform hypergraph into type ℓ Hamilton cycles, for k/2 ≤ ℓ ≤ k. For the case ℓ = k these results show that almost all edges of corresponding random and pseudo‐random hypergraphs can be packed with disjoint perfect matchings. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012
DOI：
10.1016/j.jcta.2010.02.010
发表时间：
2009-03
期刊：
J. Comb. Theory A
影响因子：
--
作者：
D. Kühn;Richard Mycroft;Deryk Osthus
通讯作者：
D. Kühn;Richard Mycroft;Deryk Osthus