Hamiltonian Paths and Cycles in Some 4-Uniform Hypergraphs

• DOI: 10.1007/s00373-022-02524-9
• Publication Date: 2022-07-19T04:02:47Z
• Authors: Guanwu Liu; Xiaonan Liu
• Keywords: Hamiltonian (control theory); Hypergraph

In 1999, Katona and Kierstead conjectured that if a $k$-uniform hypergraph $\cal H$ on $n$ vertices has minimum co-degree $\lfloor \frac{n-k+3}{2}\rfloor$, i.e., each set of $k-1$ vertices is contained in at least $\lfloor \frac{n-k+3}{2}\rfloor$ edges, then it has a Hamiltonian cycle. Rödl, Ruciński and Szemerédi in 2011 proved that the conjecture is true when $k=3$ and $n$ is large. We show that this Katona-Kierstead conjecture holds if $k=4$, $n$ is large, and $V({\cal H})$ has a partition $A$, $B$ such that $|A|=\lceil n/2\rceil$, $|\{e\in E({\cal H}):|e \cap A|=2\}| <εn^4$ for a fixed small constant $ε>0$.