Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$.

Is it possible that there exists an absolute constant $C>0$ and polynomial $p\in \mathbb{Q}[x]$ such that for all $k$ (or perhaps for all sufficiently large $k$) $$ R(k) = C^kp(k)? $$

Even the asymptotic behaviour of $R(k$) is not known (it is known that $\sqrt{2}^{k(1+o(1))}\leq R(k)\leq 4^{k(1+o(1)}$.) So a proof of such an exact result is certainly out of reach. But showing that there cannot be such a formula might be possible.

There are exact formulas known for related Ramsey-type functions (e.g. fractional Ramsey numbers [2] and Ramsey numbers restricted to various classes of graphs, such as planar graphs, line graphs, and perfect graphs [1,3].) As far as I can see, however, the question of an exact formula for the classical Ramsey numbers has not been considered.

[1] Belmonte, Heggernes, van't Hof and Saei, Ramsey numbers for line graphs and perfect graphs, Computing and combinatorics, 204–215, Lecture Notes in Comput. Sci., 7434, Springer, Heidelberg, 2012. http://link.springer.com/chapter/10.1007%2F978-3-642-32241-9_18

[2] Brown and Hoshino, Proof of a conjecture on fractional Ramsey numbers, J. Graph Theory 63 (2010), no. 2, 164–178. http://onlinelibrary.wiley.com/doi/10.1002/jgt.20416/pdf

[3] Steinberg and Tovey, Planar Ramsey numbers, J. Combin. Theory Ser. B 59 (1993), no. 2, 288–296

purespeculation. $\endgroup$ – Brendan McKay Nov 26 '14 at 10:43