Erdős Problem #584 — Subgraphs with pairwise short-cycle edges
Let be a graph with vertices and edges. Are there subgraphs such that
-
has edges and every two edges in are contained in a cycle of length at most , and furthermore if two edges share a vertex they are on a cycle of length , and
-
has edges and every two edges in are contained in a cycle of length at most .
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
The full conjecture remains open, but partial advances now reach sparser graphs while the strongest six-cycle requirement is still unresolved.
Erdős, Duke, and Rödl asked whether every graph with edge density contains large subgraphs whose edge pairs lie on short cycles: one of order with cycles of length at most and an additional adjacent-edge -cycle condition, and one of order with cycles of length at most .
Known results
- Duke and Erdős proved the first assertion for fixed and sufficiently large .
- Duke, Erdős, and Rödl (1984) obtained the first assertion with replacing .
- Their 1984 paper obtained the result at order , the adjacent-edge version at order , and a result at order .
- Fox and Sudakov (2008) proved the assertion when .
One-third-density threshold: recent partial progress
A forum-reported result reaches : it gives and of orders and , respectively, with the required pairwise and properties. It extends the prior range for the statement, but does not establish the adjacent-edge condition; the full problem remains open.
Current status (as of March 2026): Partial results cover fixed density and the polynomial range , but the full two-part assertion, especially the adjacent-edge condition, remains open.
Solutions 0
No solutions have been posted yet.