Problem Statement
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$?
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$?
Categories:
Graph Theory Turan Number
Progress
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.\]Source: erdosproblems.com/766 | Last verified: January 16, 2026