Minimum vertex degree conditions for loose spanning trees in 3-graphs

Yanitsa Pehova; Kalina Petrova

doi:10.5817/CZ.MUNI.EUROCOMB23-104

Minimum vertex degree conditions for loose spanning trees in 3-graphs

EUROCOMB’23

Yanitsa Pehova Kalina Petrova

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-104

PDF

Abstract

In 1995, Komlós, Sárközy and Szemerédi showed that for large $n$, every $n$-vertex graph with minimum degree at least $(1/2 + \gamma)n$ contains all spanning trees of bounded degree. We consider a generalization of this result to loose spanning hypertrees, that is, linear hypergraphs obtained by successively appending edges sharing a single vertex with a previous edge, in 3-graphs. We show that for all $\gamma$ and $\Delta$, and $n$ large, every $n$-vertex 3-uniform hypergraph of minimum vertex degree $(5/9 + \gamma)\binom{n}{2}$ contains every loose spanning tree with maximum vertex degree $\Delta$. This bound is asymptotically tight, since some loose trees contain perfect matchings.

Pages:
754–759

References

E. Buß, H. Hàn, and M. Schacht. Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs. J. Combin. Theory Ser. B, 103(6):658-678, 2013.
https://doi.org/10.1016/j.jctb.2013.07.004

H. Hàn, Y. Person, and M. Schacht. On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discrete Math., 23(2):732-748, 2009.
https://doi.org/10.1137/080729657

J. Han and Y. Zhao. Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs. Journal of Combinatorial Theory, Series B, 114:70-96, 2015.
https://doi.org/10.1016/j.jctb.2015.03.007

J. Komlós, G. N. Sárközy, and E. Szemerédi. Proof of a packing conjecture of Bollobás. Combin. Probab. Comput., 4(3):241-255, 1995.
https://doi.org/10.1017/S0963548300001620

M. Pavez-Signé, N. Sanhueza-Matamala, and M. Stein. Dirac-type conditions for spanning bounded-degree hypertrees. In Extended Abstracts EuroComb 2021, pages 586-592. Springer, 2021.
https://doi.org/10.1007/978-3-030-83823-2_94

M. Pavez-Signé, N. Sanhueza-Matamala, and M. Stein. Dirac-type conditions for spanning bounded-degree hypertrees, Dec 2021, arXiv:2012.09824.
https://doi.org/10.1007/978-3-030-83823-2_94

C. Reiher, V. Rödl, A. Ruciński, M. Schacht, and E. Szemerédi. Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs. Proceedings of the London Mathematical Society, 119(2):409-439, 2019.
https://doi.org/10.1112/plms.12235

A. Treglown, D. Kühn, and D. Osthus. Matchings in 3-uniform hypergraphs of large minimum vertex degree. Electronic Notes in Discrete Mathematics, 38:813-818, 2011. The Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011.
https://doi.org/10.1016/j.endm.2011.10.036

Metrics

0

Views

0

PDF views

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

PDF