PROVED
This has been solved in the affirmative.
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].
The extremal number of the graph $H_k$ with the vertex $x$ omitted is the subject of
[1021].
View the LaTeX source
This page was last edited 05 October 2025. View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Noga Alon
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 #926, https://www.erdosproblems.com/926, accessed 2026-04-11
