Problem #128: Let $G$ be a graph with $n$ vertices such that every...

---

Progress

A problem of Erdős and Rousseau. The constant $50$ would be best possible as witnessed by a blow-up of $C_5$ or the Petersen graph.

Erdős, Faudree, Rousseau, and Schelp [EFRS94] proved that this is true with $50$ replaced by $16$. More generally, they prove that, for any $0<\alpha<1$, if every set of $\geq \alpha n$ vertices contains $>\alpha^3n^2/2$ edges then $G$ contains a triangle.

Krivelevich [Kr95] has proved this with $n/2$ replaced by $3n/5$ (and $50$ replaced by $25$).

Keevash and Sudakov [KeSu06] have proved this under the additional assumption that either $G$ has at most $n^2/12$ edges, or that $G$ has at least $n^2/5$ edges. Norin and Yepremyan [NoYe15] proved that this is true if $G$ has at least $(1/5-c)n^2$ edges, for some constant $c>0$.

Razborov [Ra22] proved this is true if $\frac{1}{50}$ is replaced by $\frac{27}{1024}$.

See also the entry in the graphs problem collection.