Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2507.08324 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912476181823488 |
|---|---|
| author | Rao, Mengjiao Sanhueza-Matamala, Nicolás Sun, Lin Wang, Guanghui Zhou, Wenling |
| author_facet | Rao, Mengjiao Sanhueza-Matamala, Nicolás Sun, Lin Wang, Guanghui Zhou, Wenling |
| contents | The $k$-expansion of a graph $G$ is the $k$-uniform hypergraph obtained from $G$ by adding $k-2$ new vertices to every edge. We determine, for all $k > d \geq 1$, asymptotically optimal $d$-degree conditions that ensure the existence of all spanning $k$-expansions of bounded-degree trees, in terms of the corresponding conditions for loose Hamilton cycles. This refutes a conjecture by Pehova and Petrova, who conjectured that a lower threshold should have sufficed. The reason why the answer is off from the conjectured value is an unexpected `parity obstruction': all spanning $k$-expansions of trees with only odd degree vertices require larger degree conditions to embed. We also show that if the tree has at least one even-degree vertex, the codegree conditions for embedding its $k$-expansion become substantially smaller. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_08324 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Degree conditions for spanning expansion hypertrees Rao, Mengjiao Sanhueza-Matamala, Nicolás Sun, Lin Wang, Guanghui Zhou, Wenling Combinatorics The $k$-expansion of a graph $G$ is the $k$-uniform hypergraph obtained from $G$ by adding $k-2$ new vertices to every edge. We determine, for all $k > d \geq 1$, asymptotically optimal $d$-degree conditions that ensure the existence of all spanning $k$-expansions of bounded-degree trees, in terms of the corresponding conditions for loose Hamilton cycles. This refutes a conjecture by Pehova and Petrova, who conjectured that a lower threshold should have sufficed. The reason why the answer is off from the conjectured value is an unexpected `parity obstruction': all spanning $k$-expansions of trees with only odd degree vertices require larger degree conditions to embed. We also show that if the tree has at least one even-degree vertex, the codegree conditions for embedding its $k$-expansion become substantially smaller. |
| title | Degree conditions for spanning expansion hypertrees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.08324 |