Problem #917: Let $k\geq 4$ and $f_k(n)$ be the largest number of edges...

---

Progress

Erdős [Er93] wrote 'I learned of this definition from Dirac in 1949 and immediately asked whether $f_k(n)=o(n^2)$. To my great surprise Dirac constructed a $6$ critical graph on $n$ vertices with more than $\frac{n^2}{4}$ edges.' In fact Dirac [Di52] proved\[f_6(4n+2) \geq 4n^2+8n+3,\]as witnessed by taking two disjoint copies of $C_{2n+1}$ and adding all edges between them.

Erdős [Er69b] observed that Dirac's construction generalises to show that, if $3\mid k$, there are infinitely many values of $n$ (those of the shape $mk/3$ where $m$ is odd) such that\[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{k/3}\right)n^2 + n.\]Toft [To70] proved that $f_k(n)\gg_k n^2$ for $k\geq 4$.

Constructions of Stiebitz [St87] show that, for $k\geq 6$, there exist infinitely many values of $n$ such that\[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor+\delta_k}\right)n^2\]where $\delta_k=0$ if $k\equiv 0\pmod{3}$, $\delta_k=1/7$ if $k\equiv 1\pmod{3}$, and $\delta_k\equiv 24/69$ if $k\equiv 2\pmod{3}$, which disproves Erdős' conjectured asympotic for $k\not\equiv 0\pmod{3}$.

Stiebitz also proved the general upper bound\[f_k(n) < \mathrm{ex}(n;K_{k-1})\sim \frac{1}{2}\left(1-\frac{1}{k-2}\right)n^2\]for large $n$. Luo, Ma, and Yang [LMY23] have improved this upper bound to\[f_k(n) \leq \frac{1}{2}\left(1-\frac{1}{k-2}-\frac{1}{36(k-1)^2}+o(1)\right)n^2\]See also [944] and [1032].