Number of the records: 1
On sufficient conditions for spanning structures in dense graphs
- 1.0573793 - ÚI 2024 US eng V - Research Report
Lang, R. - Sanhueza-Matamala, Nicolás
On sufficient conditions for spanning structures in dense graphs.
Cornell University: Cornell University, 2023. 68 s. arXiv.org e-Print archive, arXiv:2110.14547.
R&D Projects: GA ČR(CZ) GA19-08740S
Institutional support: RVO:67985807
https://arxiv.org/abs/2110.14547
We study structural conditions in dense graphs that guarantee the existence of vertex-spanning substructures such as Hamilton cycles. It is easy to see that every Hamiltonian graph is connected, has a perfect fractional matching and, excluding the bipartite case, contains an odd cycle. A simple consequence of the Robust Expander Theorem of Kühn, Osthus and Treglown tells us that any large enough graph that robustly satisfies these properties must already be Hamiltonian. Our main result generalises this phenomenon to powers of cycles and graphs of sublinear bandwidth subject to natural generalisations of connectivity, matchings and odd cycles.
This answers a question of Ebsen, Maesaka, Reiher, Schacht and Schülke and solves the embedding problem that underlies multiple lines of research on sufficient conditions for spanning structures in dense graphs. As applications, we recover and establish Bandwidth Theorems in a variety of settings including Ore-type degree conditions, Pósa-type degree conditions, deficiency-type conditions, locally dense and inseparable graphs, multipartite graphs as well as robust expanders.
Permanent Link: https://hdl.handle.net/11104/0344148
File Download Size Commentary Version Access 0573793-arx-oa.pdf 1 938.5 KB https://arxiv.org/abs/2110.14547 Author´s preprint open-access
Number of the records: 1