The bounds $R(3,k)\asymp k^2/\log k$ (see [165]) imply $f(n) \asymp (n/\log n)^{1/2}$. The best bounds available are\[(1-o(1))(n/\log n)^{1/2}\leq f(n) \leq (2+o(1))(n/\log n)^{1/2}.\]The upper bound is due to Davies and Illingworth [DaIl22], the lower bound follows from a construction of Hefty, Horn, King, and Pfender [HHKP25].

One can ask a similar question for the maximum possible chromatic number of a triangle-free graph on $m$ edges. Let this be $g(m)$. Davies and Illingworth [DaIl22] prove\[g(m) \leq (3^{5/3}+o(1))\left(\frac{m}{(\log m)^2}\right)^{1/3}.\]Kim [Ki95] gave a construction which implies $g(m) \gg (m/(\log m)^2)^{1/3}$.

View the LaTeX source

This page was last edited 26 October 2025.