Cover 3-uniform hypergraphs by vertex-disjoint tight paths
arXiv:2003.11686
Abstract
Let be an -vertex 3-uniform hypergraph such that every pair of vertices is in at least edges. We show that contains two vertex-disjoint tight paths whose union covers the vertex set of . 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 can be made Hamiltonian by adding at most two vertices and all triples intersecting them.
arXiv comment19 pages, revision based on referee comments. arXiv admin note: text overlap with arXiv:1411.4957 by other authors
References in corpus (5)
- Hamilton l-cycles in uniform hypergraphs
- Minimum vertex degree conditions for loose Hamilton cycles in -uniform hypergraphs
- Hamilton cycles in graphs and hypergraphs: an extremal perspective
- Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs
- Forcing large tight components in 3-graphs