Nemanja Draganić

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

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^*n)}$ contains such a subgraph, and use this local expansion to b...