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^{ω(\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\in\mathbb N$, we prove that every graph satisfying this average-degree condition contains $k$ pairwise edge-disjoint cycles…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.16572
curl -X POST /api/v1/records/arxiv/2610.16572/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16572/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'