On sufficient conditions for spanning structures in dense graphs

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 Kuhn, 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 Schulke 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, Posa-type degree conditions, deficiency-type conditions, locally dense and inseparable graphs, multipartite graphs as well as robust expanders.

Automated summary

We study conditions in dense graphs that guarantee the existence of vertex-spanning substructures such as Hamilton cycles. 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 resolves the embedding problem underlying research on sufficient conditions for spanning structures in dense graphs. As applications, we establish various Bandwidth Theorems in different settings, including Ore-type degree conditions, Posa-type degree conditions, deficiency-type conditions, locally dense and inseparable graphs, multipartite graphs and robust expanders.