Erdős Problem #920

declared status 'open'. Formalized: yes. Let $g_k(n)$ denote the largest possible chromatic number of a graph with $n$ vertices which contains no $K_k$. Is it true that, for $k\geq 4$,$$g_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^c}$$for some constant $c>0$? Current best: 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 [986]) 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}}.$$See [1013] for the case $k=3$. Prize: no. Tags: chromatic number, graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.