Logo
All Random Solved Random Open
SOLVED
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$.
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].

Additional thanks to: Noga Alon