Hamilton cycles in hypergraphs below the Dirac threshold

DOI10.1016/J.JCTB.2018.04.010MaRDI QIDQ1791707zbMATH OpenOpenAlexWikidataFDO

Authors Frederik Garbe, Richard Mycroft

Publication date 11 October 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.03101, http://pure-oai.bham.ac.uk/ws/files/48787510/cyclesbelowdirac.pdf

zbMATH Keywords

hypergraphsHamilton cycles

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65)

Abstract: 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 $kgeq3$, giving a series of reductions to show that it is NP-hard to determine whether a $k$-uniform hypergraph $H$ with minimum degree $delta(H)geqfrac12|V(H)|-O(1)$ contains a tight Hamilton cycle. It is therefore unlikely that a similar characterisation can be obtained for tight Hamilton cycles.

Recommendations

• scientific article; zbMATH DE number 6829379
• Tight Hamilton cycles in random uniform hypergraphs
• Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
• On Hamiltonian cycles in hypergraphs with dense link graphs
• Counting Hamilton cycles in Dirac hypergraphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3641483 (Why is no real title available?)
• scientific article; zbMATH DE number 6829379 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Families of triples with high minimum degree are Hamiltonian
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian chains in hypergraphs
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• Loose Hamilton cycles in hypergraphs
• Loose Hamiltonian cycles forced by large \((k-2)\)-degree-approximate version
• Matchings in hypergraphs of large minimum degree
• Minimum codegree threshold for Hamilton \(\ell\)-cycles in \(k\)-uniform hypergraphs
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• On Sets of Acquaintances and Strangers at any Party
• On extremal hypergraphs for Hamiltonian cycles
• On extremal problems of graphs and generalized graphs
• On the Hamiltonicity of triple systems with high minimum degree
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• Paths, Trees, and Flowers
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Polynomial-time perfect matchings in dense hypergraphs
• Recent advances on Dirac-type problems for hypergraphs
• Reducibility among combinatorial problems
• Some Theorems on Abstract Graphs
• Some simplified NP-complete graph problems
• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• Tight Codegree Condition for the Existence of Loose Hamilton Cycles in 3-Graphs

Cited in

(6)

• Thin Hamiltonian cycles on Archimedean graphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
• Minimum degree thresholds for Hamilton \((k/2)\)-cycles in \(k\)-uniform hypergraphs
• Hamilton -cycles in randomly perturbed hypergraphs
• Compatible Hamilton cycles in Dirac graphs

This page was built for publication: Hamilton cycles in hypergraphs below the Dirac threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1791707)