A linear bound for nested cycles without geometric crossings
Abstract
Cycles C1,…,Ck in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, V(Ck)⊆⋯⊆ V(C1), and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let fk(n) be the least number of edges that forces such a family in every n-vertex graph. Gil Fernández, Kim, Kim and Liu proved that f2(n)=O(n), answering a question of Erdős, and asked whether fk(n)=Ok(n) for every fixed k. We prove this for all k. The proof selects the inner cycles together with a disjoint subgraph that supplies their external neighbours. A reselection argument gives disjoint paths from every inner-cycle vertex to any sufficiently large target set. Sublinear expansion and a rooted clique minor then allow the vertices to be joined in the required cyclic order.
Related
- Counting hypergraphs without linear cycles of fixed length
- Planarity and number of crossings in general models of random geometric graphs
- Geometric (1+ε)-Spanners with Few Crossings
- New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles
- Non-Wellfounded and Cyclic Proofs for LTL: A Syntactic Correspondence with Linear Nested Sequents
BibTeX
@misc{ai2026linear,
title = {{A linear bound for nested cycles without geometric crossings}},
author = {Jiangdong Ai and Gregory Gutin and Yiming Hao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02234},
eprint = {2609.02234},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02234},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A linear bound for nested cycles without geometric crossings
AU - Jiangdong Ai
AU - Gregory Gutin
AU - Yiming Hao
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.02234
UR - https://arxiv.org/abs/2609.02234
AB - Cycles C_1,…,C_k in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, V(C_k)⊆⋯⊆ V(C_1), and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let f_k(n) be the least number of edges that forces such a family in every n-vertex graph. Gil Fernández, Kim, Kim and Liu proved that f_2(n)=O(n), answering a question of Erdős, and asked whether f_k(n)=O_k(n) for every fixed k. We prove this for all k. The proof selects the inner cycles together with a disjoint subgraph that supplies their external neighbours. A reselection argument gives disjoint paths from every inner-cycle vertex to any sufficiently large target set. Sublinear expansion and a rooted clique minor then allow the vertices to be joined in the required cyclic order.
ER -