{"id":"arxiv/2606.06522","url":"https://arxiv.org/abs/2606.06522","tags":["math.CO","cs.DM","math.PR"],"score":0,"title":"On the Duke--Erdős--Rödl Problem at the One-Third Threshold","domain":"math.CO","source":"arxiv","authors":["Eric Li"],"reviews":0,"subject":"math.CO","summary":"Let $G$ be an $n$-vertex graph with $e(G)\\ge n^2/k$. We prove a self-contained internal short-cycle core theorem at the threshold $k\\le n^{1/3}$: the graph $G$ contains a subgraph $H_6$ with $Ω(n^2/k^3)$ edges in which every two distinct edges lie together on a cycle of length at most $6$ contained in $H_6$, and a subgraph $H_8$ with $Ω(n^2/k^2)$ edges in which every two distinct edges lie together on a cycle of length at most $8$ contained in $H_8$. In density notation $ρ=e(G)/n^2$, this gives internal cores of sizes $Ω(ρ^3n^2)$ and $Ω(ρ^2n^2)$ throughout the range $ρ\\ge n^{-1/3}$. The…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-02","reactions":{}}