Embedding loose spanning trees in 3-uniform hypergraphs
Pehova, Yani; and Petrova, Kalina
Embedding loose spanning trees in 3-uniform hypergraphs.
Journal of Combinatorial Theory, Series B, 168.
47 - 67.
ISSN 0095-8956
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 |
|---|---|
| Keywords | external graph theory,hypergraphs,spanning trees,minimum degree thresholds,dirac-type theorems,absorption,hypergraph regularity lemma,Dirac-type theorems,Hypergraph regularity lemma,Absorption,Minimum degree thresholds,Spanning trees,Extremal graph theory,Hypergraphs,EP/V038168/1,CRSII5 173721 |
| Departments | Mathematics |
| DOI | 10.1016/j.jctb.2024.04.003 |
| Date Deposited | 02 May 2024 11:18 |
| URI | https://researchonline.lse.ac.uk/id/eprint/122872 |
Explore Further
- https://www.lse.ac.uk/Mathematics/people/Yani-Pehova (Author)
- http://www.scopus.com/inward/record.url?scp=85192184319&partnerID=8YFLogxK (Scopus publication)
- 10.1016/j.jctb.2024.04.003 (DOI)
