Embedding loose spanning trees in 3-uniform hypergraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916231021330432 |
|---|---|
| author | Pehova, Yanitsa Petrova, Kalina |
| author_facet | Pehova, Yanitsa Petrova, Kalina |
| contents | 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 + γ)\binom{n}{2}$ contains every loose spanning tree $T$ with maximum vertex degree $Δ$. This bound is asymptotically tight, since some loose trees contain perfect matchings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_09630 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Embedding loose spanning trees in 3-uniform hypergraphs Pehova, Yanitsa Petrova, Kalina Combinatorics 05C35, 05Dxx, 05Cxx 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 + γ)\binom{n}{2}$ contains every loose spanning tree $T$ with maximum vertex degree $Δ$. This bound is asymptotically tight, since some loose trees contain perfect matchings. |
| title | Embedding loose spanning trees in 3-uniform hypergraphs |
| topic | Combinatorics 05C35, 05Dxx, 05Cxx |
| url | https://arxiv.org/abs/2301.09630 |