Erdős Problem #584 — Let $G$ be a graph with $n$ vertices and $\delta n^{2}$ edges.

Erdős, Duke, and Rödl asked whether every graph with edge density $\delta$ contains large subgraphs whose edge pairs lie on short cycles: one of order $\Omega(\delta^3 n^2)$ with cycles of length at most $6$ and an additional adjacent-edge $4$-cycle condition, and one of order $\Omega(\delta^2 n^2)$ with cycles of length at most $8$.

Known results

• Duke and Erdős proved the first assertion for fixed $\delta$ and sufficiently large $n$.
• Duke, Erdős, and Rödl (1984) obtained the first assertion with $\delta^5$ replacing $\delta^3$.
• Their 1984 paper obtained the $C_{ule6}$ result at order $n^{2-3\varepsilon}$, the adjacent-edge version at order $n^{2-5\varepsilon}$, and a $C_{ule12}$ result at order $n^{2-2\varepsilon}$.
• Fox and Sudakov (2008) proved the $C_{ule8}$ assertion when $\delta>n^{-1/5}$.

One-third-density threshold: recent partial progress

A forum-reported result reaches $rhoge n^{-1/3}$: it gives $H_6$ and $H_8$ of orders $\Omega(\rho^3n^2)$ and $\Omega(\rho^2n^2)$, respectively, with the required pairwise $C_{ule6}$ and $C_{ule8}$ properties. It extends the prior $n^{-1/5}$ range for the $C_{ule8}$ statement, but does not establish the adjacent-edge $C_4$ condition; the full problem remains open.

Current status (as of March 2026): Partial results cover fixed density and the polynomial range $rhoge n^{-1/3}$, but the full two-part assertion, especially the adjacent-edge $C_4$ condition, remains open.