Dirac-type conditions for spanning bounded-degree hypertrees
Preprint
Abstract
We prove that for fixed $k$, every $k$-uniform hypergraph on $n$ vertices and of minimum codegree at least $n/2+o(n)$ contains every spanning tight $k$-tree of bounded vertex degree as a sub\-graph. This generalises a well-known result of Koml\'os, S\'ark\"ozy and Szemer\'edi for graphs. Our result is asymptotically sharp. We also prove an extension of our result to hypergraphs that satisfy some weak quasirandomness conditions.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Hypergraphs not containing a tight tree with a bounded trunk II: 3-trees with a trunk of size 2Discrete Applied Mathematics, 2020
- Universality for bounded degree spanning trees in randomly perturbed graphsRandom Structures & Algorithms, 2019
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems2019
- Tight cycles and regular slices in dense hypergraphsJournal of Combinatorial Theory, Series A, 2017
- Forbidding Hamilton cycles in uniform hypergraphsJournal of Combinatorial Theory, Series A, 2016
- An approximate Dirac-type theorem for k-uniform hypergraphsCombinatorica, 2008
- Random Graphs2000
- Quasi-random graphsCombinatorica, 1989
- Exact solution of some Turán-type problemsJournal of Combinatorial Theory, Series A, 1987
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964