Problem Statement
Is it true that, for every $k\geq 3$, there is a constant $c_k>0$ such that\[\mathrm{ex}(n,G_k) \ll n^{3/2-c_k},\]where $G_k$ is the bipartite graph between $\{y_1,\ldots,y_k\}$ and $\{z_1,\ldots,z_{\binom{k}{2}}\}$, with each $z_j$ joined to a unique pair of $y_i$?
Categories:
Graph Theory
Progress
A conjecture of Erdős and Simonovits, who proved (in unpublished work) that in such a result one must have $c_k\to 0$ as $k\to \infty$. Erdős [Er71] could not even prove whether $\mathrm{ex}(n,G_k)=o(n^{3/2})$.When $k=3$ the graph $G_3$ is the $6$-cycle $C_6$, for which Erdős [Er64c] and Bondy and Simonovits [BoSi74] proved $\mathrm{ex}(n,C_6)\ll n^{7/6}$ (see [572]).
The graph $G_k$ is the graph $H_k$ of [926] with the vertex $x$ omitted.
Source: erdosproblems.com/1021 | Last verified: January 19, 2026