Cover 3-uniform hypergraphs by vertex-disjoint tight paths

Abstract

Let $H$ be an $n$-vertex 3-uniform hypergraph such that every pair of vertices is in at least $n/3+o(n)$ edges. We show that $H$ contains two vertex-disjoint tight paths whose union covers the vertex set of $H$. The quantity two here is best possible and the degree condition is asymptotically best possible. This result also has an interpretation as the \emph{deficiency problems}, recently introduced by Nenadov, Sudakov and Wagner: every such $H$ can be made Hamiltonian by adding at most two vertices and all triples intersecting them.

19 pages, revision based on referee comments. arXiv admin note: text overlap with arXiv:1411.4957 by other authors

References in corpus (3)

• Minimum vertex degree conditions for loose Hamilton cycles in $3$-uniform hypergraphs
• Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs
• Forcing large tight components in 3-graphs