Erdős Problems

Tags Prizes

OPEN

Let $f(n;k,l)=\min \mathrm{ex}(n;G)$, where $G$ ranges over all graphs with $k$ vertices and $l$ edges.

Give good estimates for $f(n;k,l)$ in the range $k<l\leq k^2/4$. For fixed $k$ and large $n$ is $f(n;k,l)$ a strictly monotone function of $l$?

Dirac and Erdős proved independently that when $l=\lfloor k^2/4\rfloor+1$ \[f(n;k,l)\leq \lfloor n^2/4\rfloor+1.\]