Erdős Problems

Tags Prizes

OPEN

Let $G$ be a graph with $n$ vertices and $\delta n^{2}$ edges. Are there subgraphs $H_1,H_2\subseteq G$ such that

$H_1$ has $\gg \delta^3n^2$ edges and every two edges in $H_1$ are contained in a cycle of length at most $6$, and furthermore if two edges share a vertex they are on a cycle of length $4$, and
$H_2$ has $\gg \delta^2n^2$ edges and every two edges in $H_2$ are contained in a cycle of length at most $8$.

A problem of Erdős, Duke, and Rödl. Duke and Erdős [DuEr83], who proved the first if $n$ is sufficiently large depending on $\delta$. The real challenge is to prove this when $\delta=n^{-c}$ for some $c>0$. Duke, Erdős, and Rödl [DER84] proved the first statement with a $\delta^5$ in place of a $\delta^3$.

Fox and Sudakov [FoSu08b] have proved the second statement when $\delta >n^{-1/5}$.