Blowing up Dirac's theorem

Abstract

We show that every graph $G$ on $n$ vertices with $\hat{I}´(G)\ge (1/2+\epsilon )n$ is spanned by a complete blow-up of a cycle with clusters of nearly uniform size $\hat{I}\text{c◯}(\log n)$. The proof is based on a recently introduced approach for finding vertex-spanning substructures via blow-up covers.

12 pages + 5 page appendix. Accepted to BLMS