Problem Statement
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}?\]
Categories:
Graph Theory
Progress
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)}.\]Source: erdosproblems.com/813 | Last verified: January 16, 2026