Polylogarithmic Bounds for Nested Cycles without Geometric Crossings
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910245533515776 |
|---|---|
| author | Xu, Yue Zeng, Jiasheng Zhang, Xiao-Dong |
| author_facet | Xu, Yue Zeng, Jiasheng Zhang, Xiao-Dong |
| contents | A problem of Erdős asks for extremal conditions forcing edge-disjoint cycles with a prescribed nested structure. In the geometric version, the nesting is required to be noncrossing with respect to the cyclic orders. Fernández, Kim, Kim and Liu proved that constant average degree forces two such cycles. We prove a polylogarithmic bound for the natural multi-layer version: for every fixed $k\ge 3$, every sufficiently large $n$-vertex graph with at least \[
C_k n(\log n)^{k-1}(\log\log n)^{k-3} \] edges contains $k$ pairwise edge-disjoint nested cycles without geometric crossings. The proof combines the robust sublinear expander framework of Alon, Bucić, Sauermann, Zakharov and Zamir with a controlled wrapping lemma that permits the layers to be built successively with controlled length. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_22232 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polylogarithmic Bounds for Nested Cycles without Geometric Crossings Xu, Yue Zeng, Jiasheng Zhang, Xiao-Dong Combinatorics 05C38 A problem of Erdős asks for extremal conditions forcing edge-disjoint cycles with a prescribed nested structure. In the geometric version, the nesting is required to be noncrossing with respect to the cyclic orders. Fernández, Kim, Kim and Liu proved that constant average degree forces two such cycles. We prove a polylogarithmic bound for the natural multi-layer version: for every fixed $k\ge 3$, every sufficiently large $n$-vertex graph with at least \[ C_k n(\log n)^{k-1}(\log\log n)^{k-3} \] edges contains $k$ pairwise edge-disjoint nested cycles without geometric crossings. The proof combines the robust sublinear expander framework of Alon, Bucić, Sauermann, Zakharov and Zamir with a controlled wrapping lemma that permits the layers to be built successively with controlled length. |
| title | Polylogarithmic Bounds for Nested Cycles without Geometric Crossings |
| topic | Combinatorics 05C38 |
| url | https://arxiv.org/abs/2605.22232 |