Graver and Yackel [GrYa68] proved that \[g_k(n) \ll \left(n\frac{\log\log n}{\log n}\right)^{1-\frac{1}{k-1}}.\] Erdős [Er59b] proved that \[g_3(n) \gg \frac{n^{1/2}}{\log n},\] by proving $R(3,m)\gg (m/\log m)^2$. Shearer's lower bound for $R(3,m)$ (see [165]) improves this to \[g_3(n) \gg \left(\frac{n}{\log n}\right)^{1/2}.\]

The lower bound $R(4,m) \gg m^3/(\log m)^4$ of Mattheus and Verstraete [MaVe23] (see [166]) implies \[g_4(n) \gg \frac{n^{2/3}}{(\log n)^{4/3}}.\] In general it is known (see [BoKe10]) that \[R(k,m)\gg (\log m)^{-O_k(1)}m^{\frac{k+1}{2}}\] which implies \[g_k(n) \gg \frac{n^{1-\frac{2}{k+1}}}{(\log n)^{c_k}}.\]