NESTED CYCLES WITH NO GEOMETRIC CROSSINGS

Abstract

In 1975, Erdős asked the following question: what is the smallest function f (n) for which all graphs with n vertices and f (n) edges contain two edge-disjoint cycles C1 and C2, such that the vertex set of C2 is a subset of the vertex set of C1 and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound f (n) = O(n) using sublinear expanders. © 2022 by the authors under Creative Commons Attribution 3.0 License (CC BY 3.0).