Hamiltonicity in randomly perturbed hypergraphs

被引:14
作者
Han, Jie [1 ]
Zhao, Yi [2 ]
机构
[1] Univ Rhode Isl, Dept Math, 5 Lippitt Rd, Kingston, RI 02881 USA
[2] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA
基金
巴西圣保罗研究基金会;
关键词
Hamiltonian cycle; Random hypergraph; Perturbed hypergraph; DIRAC-TYPE THEOREM; L-CYCLES; THRESHOLD;
D O I
10.1016/j.jctb.2019.12.005
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For integers k >= 3 and 1 <= l <= k - 1, we prove that for any alpha > 0, there exist epsilon > 0 and C > 0 such that for sufficiently large n is an element of (k - l)N, the union of a k-uniform hypergraph with minimum vertex degree alpha n(k-1) and a binomial random k-uniform hypergraph G((k)) (n, p) with p >= n(-(k-l)-epsilon) for l >= 2 and p >= Cn(-(k-1)) for l = 1 on the same vertex set contains a Hamiltonian l-cycle with high probability. Our result is best possible up to the values of epsilon and C and answers a question of Krivelevich, Kwan and Sudakov. (C) 2020 Elsevier Inc. All rights reserved.
引用
收藏
页码:14 / 31
页数:18
相关论文
共 36 条
[1]   Tilings in Randomly Perturbed Dense Graphs [J].
Balogh, Jozsef ;
Treglown, Andrew ;
Wagner, Adam Zsolt .
COMBINATORICS PROBABILITY & COMPUTING, 2019, 28 (02) :159-176
[2]  
Bastos J.O., 2018, CONTRIB DISCRETE MAT, V13
[3]   LOOSE HAMILTONIAN CYCLES FORCED BY LARGE (k-2)-DEGREE-APPROXIMATE VERSION [J].
Bastos, Josefran de Oliveira ;
Mota, Guilherme Oliveira ;
Schacht, Mathias ;
Schnitzer, Jakob ;
Schulenburg, Fabian .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (04) :2328-2347
[4]   Powers of tight Hamilton cycles in randomly perturbed hypergraphs [J].
Bedenknecht, Wiebke ;
Han, Jie ;
Kohayakawa, Yoshiharu ;
Mota, Guilherme O. .
RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (04) :795-807
[5]  
Bennett P., 2017, ARXIV E PRINTS
[6]   Universality for bounded degree spanning trees in randomly perturbed graphs [J].
Boettcher, Julia ;
Han, Jie ;
Kohayakawa, Yoshiharu ;
Montgomery, Richard ;
Parczyk, Olaf ;
Person, Yury .
RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (04) :854-864
[7]   How many random edges make a dense graph hamiltonian? [J].
Bohman, T ;
Frieze, A ;
Martin, R .
RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (01) :33-42
[8]  
Bottcher J., PREPRINT
[9]   Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs [J].
Buss, Enno ;
Han, Hiep ;
Schacht, Mathias .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (06) :658-678
[10]   TIGHT CODEGREE CONDITION FOR THE EXISTENCE OF LOOSE HAMILTON CYCLES IN 3-GRAPHS [J].
Czygrinow, Andrzej ;
Molla, Theodore .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (01) :67-76