Erdős Problem #585 — Edge-disjoint cycles on the same vertex set
For a positive integer , let range over finite simple undirected graphs with . A cycle means a simple cycle, and two cycles are edge-disjoint if they share no edges. Define Chakraborti, Janzer, Methuku, and Montgomery (2025)
Chakraborti, Janzer, Methuku, and Montgomery (2025)
The question is to determine , the largest possible number of edges under this prohibition. Chakraborti, Janzer, Methuku, and Montgomery (2025)
Background
Erdős posed this extremal question in 1975. A lower bound comes from a construction of Pyber, Rödl, and Szemerédi: their graphs have edges and no -regular subgraph. Since the union of two edge-disjoint cycles on the same vertex set is -regular on that set, these graphs contain no forbidden pair. This connects the problem to the Erdős–Sauer problem on forcing regular subgraphs, though absence of a -regular subgraph is a sufficient construction criterion, not an equivalent reformulation of the cycle condition. Chakraborti, Janzer, Methuku, and Montgomery (2025)
Before the direct approach of Chakraborti, Janzer, Methuku, and Montgomery, upper bounds came from Turán-type results: for example, the Kővári–Sós–Turán theorem gives , while later developments using blow-ups of cycles give . The paper explains that this general Turán approach cannot improve the exponent below , making a direct method important for closing the gap with the construction. Chakraborti, Janzer, Methuku, and Montgomery (2025)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.