{"id":"arxiv/2609.02234","url":"https://arxiv.org/abs/2609.02234","tags":["math.CO","cs.DM"],"score":0,"title":"A linear bound for nested cycles without geometric crossings","domain":"math.CO","source":"arxiv","authors":["Jiangdong Ai","Gregory Gutin","Yiming Hao"],"reviews":0,"subject":"math.CO","summary":"Cycles $C_1,\\ldots,C_k$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V(C_k)\\subseteq\\cdots\\subseteq 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}