OPEN
This is open, and cannot be resolved with a finite computation.
Let $h(n)$ be minimal such that every graph on $n$ vertices where every set of $7$ vertices contains a triangle (a copy of $K_3$) must contain a clique on at least $h(n)$ vertices. Estimate $h(n)$ - in particular, do there exist constants $c_1,c_2>0$ such that\[n^{1/3+c_1}\ll h(n) \ll n^{1/2-c_2}?\]
A problem of Erdős and Hajnal, who could prove that\[n^{1/3}\ll h(n) \ll n^{1/2}.\]Bucić and Sudakov
[BuSu23] have proved\[h(n) \gg n^{5/12-o(1)}.\]
View the LaTeX source
Additional thanks to: Zach Hunter
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 #813, https://www.erdosproblems.com/813, accessed 2026-01-16
