Logo
All Random Solved Random Open
OPEN
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)}.\]

Additional thanks to: Zach Hunter