On sufficient conditions for spanning structures in dense graphs

0581958 - ÚI 2024 GB eng J - Journal Article
Lang, R. - Sanhueza-Matamala, Nicolás
On sufficient conditions for spanning structures in dense graphs.
Proceedings of the London Mathematical Society. Roč. 127, č. 3 (2023), s. 709-793. ISSN 0024-6115. E-ISSN 1460-244X
R&D Projects: GA ČR(CZ) GA19-08740S
Impact factor: 1.8, year: 2022
Method of publishing: Open access
https://doi.org/10.1112/plms.12552

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/0350096