Problem 1011

Erdős Problem #1011: declared status 'open'. Formalized: no. Let $f_r(n)$ be minimal such that every graph on $n$ vertices with $\geq f_r(n)$ edges and chromatic number $\geq r$ contains a triangle. Determine $f_r(n)$. Current best: Simonovits [Si74] notes$$\frac{\log r}{\log\log r}r^2 \ll g(r) \ll (\log r)^2r^2.$$Hunter in the comments has noted that other results imply $g(r)\asymp r^2\log r$ - in fact$$(1/2-o(1))r^2\log r\leq g(r)\leq (2+o(1))r^2\log r.$$The lower bound follows from work of Davies and Illingworth [DaIl22] (see [1104]). The upper bound follows from work of Hefty, Horn, King, and Pfender [HHKP25] on $R(3,k)$. Ren, Wang, Wang, and Yang [RWWY24] showed that, for $n\geq 150$,$$f_4(n)=\left\lfloor\frac{(n-3)^2}{4}\right\rfloor+6.$$ References [DaIl22] Davies, Ewan and Illingworth, Freddie, The {$\chi$}-{R}amsey problem for triangle-free graphs. Prize: no. Tags: graph theory.