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
Best Answer
Obviously I cannot prove it, but I think the answer is almost surely 'no'. In fact, I don't think any combination of polynomials, exponentials, and factorials will do the job: I believe you should need (at least) to have involvement of the parity mod $2$ function.
My reason for this is of course quite trivial. When you try to find a lower bound example for $R(3,4)$, you observe that neighbourhoods are independent hence the maximum degree of the graph you are constructing is three. Then you note that every vertex has at most five non-neighbours, otherwise you use the value of $R(3,3)$ in the non-neighbourhood. So you think: OK, I should have a $3$-regular graph on $9$ vertices. Unfortunately this doesn't exist because $3$ and $9$ are both odd, and you are forced to use $8$ vertices.
I would expect this kind of parity obstacle to show up quite often.