Embedding loose spanning trees in 3-uniform hypergraphs
Pehova, Y. & Petrova, K.
(2024).
Embedding loose spanning trees in 3-uniform hypergraphs.
Journal of Combinatorial Theory, Series B,
168, 47 - 67.
https://doi.org/10.1016/j.jctb.2024.04.003
In 1995, Komlós, Sárközy and Szemerédi showed that every large n-vertex graph with minimum degree at least (1/2+γ)n contains all spanning trees of bounded degree. We consider a generalization of this result to loose spanning hypertrees in 3-graphs, that is, linear hypergraphs obtained by successively appending edges sharing a single vertex with a previous edge. We show that for all γ and Δ, and n large, every n-vertex 3-uniform hypergraph of minimum vertex degree (5/9+γ)(n2) contains every loose spanning tree T with maximum vertex degree Δ. This bound is asymptotically tight, since some loose trees contain perfect matchings.
| Item Type | Article |
|---|---|
| Copyright holders | © 2024 The Authors |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1016/j.jctb.2024.04.003 |
| Date Deposited | 02 May 2024 |
| Acceptance Date | 25 Apr 2024 |
| URI | https://researchonline.lse.ac.uk/id/eprint/122872 |
Explore Further
- https://www.lse.ac.uk/Mathematics/people/Yani-Pehova (Author)
- https://www.scopus.com/pages/publications/85192184319 (Scopus publication)
- https://www.sciencedirect.com/journal/journal-of-c... (Official URL)
