Hamilton l-cycles in uniform hypergraphs
Hamilton l-cycles in uniform hypergraphs
复制标题
DOI：
10.1016/j.jcta.2010.02.010
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
D. Kühn;Richard Mycroft;Deryk Osthus
中科院分区：
文献类型：
--
作者：
D. Kühn;Richard Mycroft;Deryk Osthus
我们说k-一致超图C是n-圈，如果存在C的顶点的循环序，使得C的每条边由k个连续顶点组成，并且使得每对连续边（在边的自然序中）精确相交于n个顶点。证明了：若1 <$k <k且k− <$k不整除k，则任意n阶k一致超图的最小度至少为n <$kk− <$k（k− <$k）+o（n），都包含汉密尔顿圈.这证实了Hàn和Schacht的一个猜想。结合Rödl、Rucienski和Szemerédi的结果，我们的结果渐近地确定了对于1 ≤ k ≤ k的任意n，强制生成一个n-圈的最小度。
We say that a k-uniform hypergraph C is an ℓ-cycle if there exists a cyclic ordering of the vertices of C such that every edge of C consists of k consecutive vertices and such that every pair of consecutive edges (in the natural ordering of the edges) intersects in precisely ℓ vertices. We prove that if 1⩽ℓ<k and k−ℓ does not divide k then any k-uniform hypergraph on n vertices with minimum degree at least n⌈kk−ℓ⌉(k−ℓ)+o(n) contains a Hamilton ℓ-cycle. This confirms a conjecture of Hàn and Schacht. Together with results of Rödl, Ruciński and Szemerédi, our result asymptotically determines the minimum degree which forces an ℓ-cycle for any ℓ with 1⩽ℓ<k.