PreprintarXiv licencearXiv
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ω(log*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∈ℕ, 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.
Related
- Concentration of bounded sparse chaoses and sparse Khatri-Rao embeddings
- A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings
- Nonlinear parameter-varying embeddings for nonlinear state estimation with application to a two-link robot manipulator
- Bayesian Implementation of the Factor‐Analytic Mixed Model and Application to Embeddings
- A Network-Structured Bayesian Hierarchical Model for Sparse Mutation-Drug Response Associations: Application to Cancer Pharmacogenomics
BibTeX
@misc{draganic2026tools,
title = {{New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles}},
author = {Nemanja Draganić},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16572},
eprint = {2610.16572},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16572},
}
RIS
TY - UNPB
TI - New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles
AU - Nemanja Draganić
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16572
UR - https://arxiv.org/abs/2610.16572
AB - 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^ω(log^*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∈ℕ, 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.
ER -