Erdős Problem #926

Let \(k\geq 4\). Is it true that \[\mathrm{ex}(n;H_k) \ll_k n^{3/2},\] where \(H_k\) is the graph on vertices \(x,y_1,\ldots,y_k,z_1,\ldots,z_{\binom{k}{2}}\), where \(x\) is adjacent to all \(y_i\) and each pair of \(y_i,y_j\) is adjacent to a unique \(z_i\). It is trivial that \(\mathrm{ex}(n;H_k)\gg n^{3/2}\) since \(H_k\) contians a \(C_4\) for \(k\geq 3\). Erdős [Er71] claimed a proof for \(k=3\). The answer is yes, proved by Füredi [Fu91], who proved that \(\mathrm{ex}(n;H_k) \ll (kn)^{3/2}\). This was improved to \(\mathrm{ex}(n;H_k) \ll kn^{3/2}\) by Alon, Krivelevich, and Sudakov [AKS03]. Since each \(H_k\) is 2-degenerate this is a special case of [146](https://www.erdosproblems.com/146). The extremal number of the graph \(H_k\) with the vertex \(x\) omitted is the subject of [1021](https://www.erdosproblems.com/1021).