Edge-disjoint cycles with the same vertex set

In 1975, Erdős asked for the maximum number of edges that an n-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turán-type results can be used to prove an upper bound of n3/2+o(1). However, this approach cannot give an upper bound better than Ω(n3/2). We show that there is an absolute constant t and some constant c=c(k) such that for each k≥2, every n-vertex graph with at least cn(log⁡n)t edges contains k pairwise edge-disjoint cycles with the same vertex set, resolving this old problem in a strong form up to a polylogarithmic factor. The well-known construction of Pyber, Rödl and Szemerédi of graphs without 4-regular subgraphs shows that there are n-vertex graphs with Ω(nlog⁡log⁡n) edges which do not contain two cycles with the same vertex set, so the polylogarithmic term in our result cannot be completely removed. Our proof combines a variety of techniques including sublinear expanders, absorption and a novel tool for regularisation, which is of independent interest. Among other applications, this tool can be used to regularise an expander while still preserving certain key expansion properties.