Problem 620

Erdős Problem #620: declared status 'open'. Formalized: no. If $G$ is a graph on $n$ vertices without a $K_4$ then how large a triangle-free induced subgraph must $G$ contain? Current best: Bollob\'{a}s and Hind [BoHi91] proved$$n^{1/2} \ll f(n) \ll n^{7/10+o(1)}.$$Krivelevich [Kr94] improved this to$$n^{1/2}(\log\log n)^{1/2} \ll f(n) \ll n^{2/3}(\log n)^{1/3}.$$Wolfovitz [Wo13] proved$$f(n) \ll n^{1/2}(\log n)^{120}.$$The best bounds currently known are$$n^{1/2}\frac{(\log n)^{1/2}}{\log\log n}\ll f(n) \ll n^{1/2}\log n.$$The lower bound follows from results of Shearer [Sh95], and the upper bound was proved by Mubayi and Verstraete [MuVe24]. Prize: no. Tags: graph theory.