Unbounded degree spanning hypertrees in Dirac hypergraphs
Preprint
Abstract
In 2001, Komlós, Sárközy, and Szemerédi proved that every sufficiently large $n$-vertex graph with minimum degree at least $\left(1/2+γ\right)n$ contains all spanning trees with maximum degree at most $cn/\log n$. We extend this result to hypergraphs by considering loose hypertrees, which are linear hypergraphs obtained by successively adding edges that share exactly one vertex with a previous edge. For all $k > \ell \geq 2$, we determine asymptotically optimal $\ell$-degree conditions that ensure the existence of all rooted spanning loose hypertrees, without any degree condition, in terms of the $(\ell-1)$-degree threshold for the existence of a perfect matching in $(k-1)$-graphs. As a corollary, we also asymptotically determine the $\ell$-degree threshold for the existence of bounded degree spanning loose hypertrees in $k$-graphs for $k/2 < \ell < k$, confirming a conjecture of Pehova and Petrova in this range. In our proof, we avoid the use of Szemerédi's regularity lemma.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Embedding loose spanning trees in 3-uniform hypergraphsJournal of Combinatorial Theory, Series B, 2024
- Rainbow spanning structures in graph and hypergraph systemsForum of Mathematics, Sigma, 2023
- Spanning trees in dense directed graphsJournal of Combinatorial Theory, Series B, 2022
- Tree Containment and Degree Conditions2020
- Spanning trees in random graphsAdvances in Mathematics, 2019
- Universality for bounded degree spanning trees in randomly perturbed graphsRandom Structures & Algorithms, 2019
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs IIJournal of Combinatorial Theory, Series A, 2013
- Tight Bounds for Embedding Bounded Degree Trees2010
- Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large CodegreeGraphs and Combinatorics, 2008
- Spanning Trees in Dense GraphsCombinatorics, Probability and Computing, 2001