OPEN
This is open, and cannot be resolved with a finite computation.
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$?
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.
View the LaTeX source
This page was last edited 05 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1021, https://www.erdosproblems.com/1021, accessed 2026-01-17
