New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles

Abstract

We introduce \emph{hybrid expanders}, sparse graphs which combine sublinear expansion across all scales with strong constant-factor expansion on smaller, polylogarithmic sets. We show that every $n$-vertex graph of average degree at least $2^{\omega ({\log }^{\ast }n)}$ contains such a subgraph, and use this local expansion to bring into the sparse setting tree-embedding and rollback tools more commonly associated with random or pseudorandom graphs. As an application, for fixed $k\in \mathbb{N}$, we prove that every graph satisfying this average-degree condition contains $k$ pairwise edge-disjoint cycles with nested vertex sets and compatible cyclic orders, resolving up to a quasi-constant factor a problem of Thomassen, originating in work of Erdős.

arXiv comment18 pages, 1 figure