An approximate Dirac-type theorem for \(k\)-uniform hypergraphs (Q949794): Difference between revisions

A \(k\)-uniform hypergraph is said to be hamiltonian if for some cyclic ordering of its vertex set, every \(k\) consecutive vertices form an edge. In this paper an approximate version for uniform hypergraphs of an analogous result to Dirac's theorem for graphs is proved: For every \(k\geq 3\) and \(\gamma>0\), and for all \(n\) large enough, a sufficient condition for an \(n\)-vertex \(k\)-uniform hypergraph to be hamiltonian is that each \((k-1)\)-element set of vertices is contained in at least \((1/2+\gamma)n\) edges. This result is related to the following conjecture by \textit{Gy.~Y.~Katona} and \textit{H.~A.~Kierstead} [J. Graph Theory 30, 205-212 (1999; Zbl 0924.05050)]: Let \(H\) be a \(k\)-graph with \(n\geq k+1\) vertices. If every \((k-1)\)-element set of vertices is contained in at least \(\lfloor n/2\rfloor\) edges, then \(H\) is hamiltonian.