Abstract
We prove that for fixed k, every k-uniform hypergraph on n vertices and of minimum codegree at least \(n/2+o(n)\) contains every spanning tight k-tree of bounded vertex degree as a subgraph. This generalises a well-known result of Komlós, Sárközy and Szemerédi for graphs. Our result is asymptotically sharp .
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Ajtai, M., Komlós, J., Szemerédi, E.: On a Conjecture of Loebl, Graph Theory, Combinatorics, and Algorithms, vol. 1, 2, pp. 1135–1146. Wiley, New York (1995). (Kalamazoo, MI, 1992)
Bollobás, B.: Extremal Graph Theory. Academic Press, London (1978)
Böttcher, J., et al.: Universality for bounded degree spanning trees in randomly perturbed graphs. Random Struct. Algorithms 55(4), 854–864 (2019)
Böttcher, J., Montgomery, R., Parczyk, O., Person, Y.: Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika 66(2), 422–447 (2019)
Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. (3)2(1), 69–81 (1952)
Komlós, J., Sárközy, G.N., Szemerédi, E.: Proof of a packing conjecture of Bollobás. Combin. Probab. Comput. 4(2), 241–255 (1995)
Komlós, J., Sárközy, G.N., Szemerédi, E.: Spanning trees in dense graphs. Combin. Probab. Comput. 10(5), 397–416 (2001)
Pavez-Signé, M., Sanhueza-Matamala, N., Stein, M.: Dirac-type conditions for spanning bounded-degree hypertrees. arXiv:2012.09824 (2020)
Rödl, V., Ruciński, A., Szemerédi, E.: An approximate Dirac-type theorem for \(k\)-uniform hypergraphs. Combinatorica 28(2), 229–260 (2008)
Simonovits, M., Szemerédi, E.: Embedding graphs into larger graphs: results, methods, and problems. In: Bárány, I., Katona, G.O.H., Sali, A. (eds.) Building Bridges II. BSMS, vol. 28, pp. 445–592. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-662-59204-5_14
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Pavez-Signé, M., Sanhueza-Matamala, N., Stein, M. (2021). Dirac-Type Conditions for Spanning Bounded-Degree Hypertrees. In: Nešetřil, J., Perarnau, G., Rué, J., Serra, O. (eds) Extended Abstracts EuroComb 2021. Trends in Mathematics(), vol 14. Birkhäuser, Cham. https://doi.org/10.1007/978-3-030-83823-2_94
Download citation
DOI: https://doi.org/10.1007/978-3-030-83823-2_94
Published:
Publisher Name: Birkhäuser, Cham
Print ISBN: 978-3-030-83822-5
Online ISBN: 978-3-030-83823-2
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)