کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
11021705 | 1703088 | 2018 | 58 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hamilton cycles in hypergraphs below the Dirac threshold
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We establish a precise characterisation of 4-uniform hypergraphs with minimum codegree close to n/2 which contain a Hamilton 2-cycle. As an immediate corollary we identify the exact Dirac threshold for Hamilton 2-cycles in 4-uniform hypergraphs. Moreover, by derandomising the proof of our characterisation we provide a polynomial-time algorithm which, given a 4-uniform hypergraph H with minimum codegree close to n/2, either finds a Hamilton 2-cycle in H or provides a certificate that no such cycle exists. This surprising result stands in contrast to the graph setting, in which below the Dirac threshold it is NP-hard to determine if a graph is Hamiltonian. We also consider tight Hamilton cycles in k-uniform hypergraphs H for kâ¥3, giving a series of reductions to show that it is NP-hard to determine whether a k-uniform hypergraph H with minimum degree δ(H)â¥12|V(H)|âO(1) contains a tight Hamilton cycle. It is therefore unlikely that a similar characterisation can be obtained for tight Hamilton cycles.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 133, November 2018, Pages 153-210
Journal: Journal of Combinatorial Theory, Series B - Volume 133, November 2018, Pages 153-210
نویسندگان
Frederik Garbe, Richard Mycroft,