Packing tight Hamilton cycles in 3‐uniform hypergraphs
Packing tight Hamilton cycles in 3‐uniform hypergraphs
复制标题
将紧密的哈密尔顿循环封装在 3 均匀超图中
DOI：
10.1002/rsa.20374
复制
发表时间：
2010
影响因子：
1
通讯作者：
Po
中科院分区：
文献类型：
--
作者：
A. Frieze;Michael Krivelevich;Po
设H是一个具有n个顶点的3一致超图。紧汉密尔顿圈C ∈ H是n条边的集合，其中顶点v1，.，vn的排序使得每个连续顶点的三元组{vi，vi +1，vi +2}是C的一条边（指数被认为是模n）。我们开发了新的技术，使我们能够证明，在某些自然的伪随机条件下，几乎所有的边缘H可以覆盖的边缘不相交的紧汉密尔顿圈，n整除4。因此，我们得到了一个推论，即随机3一致超图几乎可以完全被紧汉密尔顿圈whp填满，其中n可以被4整除，p不太小。沿着这条路，我们发展了一个类似的结果，包装汉密尔顿圈的伪随机有向图与偶数个顶点。© 2011 Wiley Periodicals，Inc.随机结构算法，2011
Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ⊂ H is a collection of n edges for which there is an ordering of the vertices v1,…,vn such that every triple of consecutive vertices {vi,vi+1,vi+2} is an edge of C (indices are considered modulo n ). We develop new techniques which enable us to prove that under certain natural pseudo‐random conditions, almost all edges of H can be covered by edge‐disjoint tight Hamilton cycles, for n divisible by 4. Consequently, we derive the corollary that random 3‐uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo‐random digraphs with even numbers of vertices. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011
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
DOI：
10.1016/j.jctb.2011.10.005
发表时间：
2009-08
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Demetres Christofides;D. Kühn;Deryk Osthus
通讯作者：
Demetres Christofides;D. Kühn;Deryk Osthus
随机图的近似哈密尔顿分解
影响因子：
1
作者：
Knox F
通讯作者：
Knox F