Nested cycles with no geometric crossings
Irene Gil Fernández, Jaehoon Kim, Younjin Kim, Hong Liu · Proceedings of the American Mathematical Society Series B · 2022
In 1975, Erdős asked the following question: what is the smallest function f ( n ) f(n) for which all graphs with n n vertices and f ( n ) f(n) edges contain two edge-disjoint cycles C 1 C_1 and C 2 C_2 , such that the vertex set of C 2 C_2 is a subset of the vertex set of C 1 C_1 and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound f ( n ) = O ( n ) f(n)=O(n) using sublinear expanders.