کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
11021705 1703088 2018 58 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamilton cycles in hypergraphs below the Dirac threshold
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Hamilton cycles in hypergraphs below the Dirac threshold
چکیده انگلیسی
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
نویسندگان
, ,