2025/02/07 by Yaobin Chen, Allan Lo, Chen, Yaobin +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2502.04783
openalex publication_date 2025/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A classical result of Komlós, Sárközy and Szemerédi shows that every large n-vertex graph with minimum degree at least (1/2+γ)n contains all spanning trees of bounded degree. We generalised this result to loose spanning hypertrees in k-uniform hypergraphs, that is, linear hypergraphs obtained by subsequently adding edges sharing a single vertex with a previous edge. We give a general sufficient condition for embedding loose trees with bounded degree. In particular, we show that for all k≥ 4, every n-vertex k-uniform hypergraph with n≥ n0(k,γ, Δ) and minimum (k-2)-degree at least (1/2+γ)\binomnk-2 contains every spanning loose tree with maximum vertex degree at most Δ. This bound is asymptotically tight. This generalises a result of Pehova and Petrova, who proved the case when k=3 and of Pavez-Signé, Sanhueza-Matamala and Stein, who considered the codegree threshold for bounded degree tight trees.