Asymptotics for Ramsey Theory Ramsey Theory says that every sufficently large (but finite) complete graph having $d-$coloured edges contains a monochromatic complete subgraph with $k$ vertices.
One could ask for asymptotics: Let $A(n,d,k)$ be the minimal number of
monochromatic complete subgraphs with $k$ vertices contained in any complete graph with $n$
vertices whose edges are coloured with $d$ colours.
One has the obvious bounds: $n+1-N\leq A(n,d,k)\leq {n\choose k}\sim \frac{n^k}{k!}$
where $N$ is the corresponding Ramsey number.
There exists thus a critical exponent $\alpha$ 
such that $\lim_{n\rightarrow\infty}\frac{A(n,d,k)}{n^{\beta}}=\infty$
for all $\beta<\alpha$ and 
$\liminf_{n\rightarrow\infty}\frac{A(n,d,k)}{n^{\beta}}=0$
for all $\beta>\alpha$. 
What is $\alpha$? Perhaps the function $\frac{A(n,d,k)}{n^{\alpha}}$ has a nice behaviour?
Are there any instance where one can say anything interesting? (One has 
obviously $\alpha\geq 1$ a strict inequality would probably already be interesting.)
The same type of question can be asked for Erd\"os-Szekeres, for van der Waerden 
(with a different, much smaller but still affine lower bound) etc.
Added after Gowers solution: Gowers gave the following easy proof that $\alpha=k$.
Denote by $m=\inf\lbrace n\ \vert\ A(n,d,k)>0\rbrace$ the Ramsey number 
corresponding to our problem. Since a fixed monochromatic $k-$clique is contained
in exactly ${n-k\choose m-k}$ subsets of size $m$ we have 
$$A(n,d,k)\geq\frac{{n\choose m}}{{n-k\choose m-k}}\sim \frac{n^k}{m^k}\ .$$
The only interesting question is thus the exact value of $\lim_{n\rightarrow\infty}\frac{A(n,d,k)}{n^k}$ which exists by Gowers first argument.
 A: OK, this is an attempt to amplify the very brief sketch of what could be done with the regularity lemma. Of course, I'll still give a sketch, but I'll try to say more clearly what I mean.
First of all, the regularity lemma itself says that for every $\epsilon&gt;0$ there exists a constant $K$ such that for every graph $G$ you can partition the vertex set into $k\leq K$ sets $V_1,\dots,V_k$ of roughly equal size such that for all but $\epsilon k^2$ of the pairs $(i,j)$ the induced bipartite subgraph (or just subgraph if $i=j$) is $\epsilon$-regular. Here, $\epsilon$-regular means something like "behaves to within $\epsilon$ like a typical random graph of the same density". I won't say precisely what that means, but I hope it will be plausible that this quasirandomness property will have the consequences I claim it has.
Now if we $r$-colour a complete graph, that's the same as partitioning the edges into $r$ graphs. It turns out that a simple modification of the proof of the regularity lemma allows us to apply it to all these $r$ graphs at once, obtaining a single partition that works for all of them. (Of course, now the constant $K$ will depend on $r$ as well as on $\epsilon$.) What I mean here is that for all but $\epsilon k^2$ pairs, all $r$ of the induced bipartite subgraphs are $\epsilon$-quasirandom.
For many purposes, all random graphs of a given density behave in the same way. That is the case here, so once we have our partition the only information we really care about is the densities of the various colours in the various bipartite graphs. That is, we care about numbers like $\alpha_{ijs}$ where that is the density of edges in $V_i\times V_j$ that are coloured with colour $s$. 
Let's call a pair $(i,j)$ good if all the colour classes of edges in $V_i\times V_j$ are quasirandom. The main consequence we need of quasirandomness is that if you have $d$ of the sets $V_1,\dots,V_k$ such that all the pairs from among those $d$ sets are good, then the number of cliques of colour $s$ will be approximately $|V_{i_1}|\dots|V_{i_d}|\prod_{j,h\leq d}\alpha_{i_ji_hs}$, where $V_{i_1}\dots V_{i_d}$ are the sets in question. Since almost all pairs are good, almost all $d$-tuples generate $\binom d2$ pairs that are all good. It follows that up to some error that tends to zero with $\epsilon$, the number of monochromatic cliques, as a fraction of $n^k$, depends just on the numbers $\alpha_{ijs}$. (To see this, you just add up over all possible $d$-tuples.) It follows that the minimum number of monochromatic cliques can be found by calculating a minimum over all choices of $\alpha_{ijs}$. Since $k$ is bounded above by a number that depends on $\epsilon$ and $r$ only, this is in principle a finite problem for any given $\epsilon$, $d$ and $r$. (However, the bound on $k$ is absolutely vast, so this problem is absolutely not feasible in practice.) More to the point, it proves that $A(n,d,r)/n^d$ tends to a limit as $n$ tends to infinity with fixed $d$ and $r$. (Apologies -- I've changed your $k$ to a $d$ and your $d$ to an $r$. That's because I chose $k$ in the regularity lemma, which I now regret.)
It remains to establish that this limit isn't zero. A quick and dirty way of doing that is to make $\epsilon$ so small that there must exist $R(r,d)$ of the sets $V_i$ such that all pairs are good, where $R(d,r)$ is the number needed to get a monochromatic clique of size $d$ when you have $r$ colours. For each pair we can now choose the colour that occurs most frequently and colour that pair with that colour. Applying Ramsey's theorem, we obtain a monochromatic clique of size $d$, which translates into $d$ sets $V_{i_1}\dots V_{i_d}$ that are all quasirandomly joined in that colour with density at least $1/r$. By quasirandomness, that gives us (to within a small error) at least $r^{-\binom d2}|V_{i_1}|\dots|V_{i_d}|$. Each $V_i$ has at least $n/K$ elements, and $K$ is independent of $n$, which completes the proof. 
A: I'm not sure this is as interesting as you think. Here is a sketch that $\alpha=k$. For large enough $n$ we can apply Szemer\'edi's regularity lemma simultaneously to all the colour classes. The result is a collection of block graphs that add up to 1 everywhere (approximately). If the number of blocks is larger than the corresponding Ramsey number (plus a little bit to allow for the error) then you get a block-clique joined by block-edges all of the same colour. Then a counting lemma gives you a number of cliques that is proportional (with a very small constant of proportionality) to $n^k$. 
Actually, I'm being stupid. As I know perfectly well, since I've used it frequently, one can just average over all subgraphs with m vertices, where m is the relevant Ramsey number. Each one contains a monochromatic clique, and since m doesn't depend on n the number of cliques you end up with is proportional to $n^k$.
Essentially the same argument works for van der Waerden and many other problems.
Edit: actually, the regularity lemma comment wasn't entirely stupid, because it can be used to show that $A(n,k,d)/n^k$ tends to a limit as $n$ tends to infinity, answering another of your questions above.
